One approach to solve https://leetcode.com/problems/word-break/ is to use an array for memoization.

The solution claims that it will have a space complexity of O(N).

However, I think it should be closer to O(N^2) because at each recursive level, we do a substring operation s[start:end]. Is this accurate?

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @lru_cache
        def wordBreakMemo(s: str, word_dict: FrozenSet[str], start: int):
            if start == len(s):
                return True
            for end in range(start   1, len(s)   1):
                if s[start:end] in word_dict and wordBreakMemo(s, word_dict, end):
                    return True
            return False

        return wordBreakMemo(s, frozenset(wordDict), 0)

CodePudding user response：

However, I think it should be closer to O(N^2) because at each recursive level, we do a substring operation s[start:end]. Is this accurate?

Not in this case. Let's break down the operations in this line:

if s[start:end] in word_dict and wordBreakMemo(s, word_dict, end):

1. Take the substring s[start:end]
2. Check if the substring is in word_dict.
3. (Short circuit) If not, skip if block.
4. Call wordBreakMemo, and check return value.
5. If true, then enter if block.

The thing to notice is that the substring is not assigned to a variable, and we're done with it after step 2. It is freed at that point, before recursing. Therefore, only one substring can be allocated at a time: the one belonging to the function at the top of the stack.