这个带有记忆代码的递归的时间复杂度是多少？

Question

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakMemo(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
    }

    // a function that will compute the answer for every given state
    private boolean wordBreakMemo(String s, Set<String> wordDict, int start, Boolean[] memo) {
        //base case: null is true
        if (start == s.length()) {
            return true;
        }
        //avoid recomputation
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            //recurrence relation 
            //dp[start] = set.contains(substring(start,end)) && dp[end]
            if (wordDict.contains(s.substring(start, end)) && wordBreakMemo(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

这是一个使用带记忆的递归的 leetcode（139.word break）解决方案。 社论说时间复杂度是

O(n^3)

，其中n是输入字符串的长度。 我不明白，有人可以解释一下吗，谢谢。