Space 分词算法的复杂度

Question

解决https://leetcode.com/problems/word-break/的一种方法是使用数组进行记忆。

该解决方案声称它的 space 复杂度为 O(N)。

不过，我觉得应该更接近于O(N^2)，因为在每个递归层次上，我们都做一个子串操作s[start:end]。这准确吗？

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)

Answer 1

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?

在这种情况下不是。我们把这一行的操作分解一下：

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

取子串s[start:end]
检查子串是否在word_dict.
（短路）如果不是，跳过if块。
调用 wordBreakMemo，并检查 return 值。
如果为true，则进入if块。

需要注意的是，子字符串没有分配给变量，我们在第 2 步之后就完成了它。在递归之前，它在那个时候被释放了。因此一次只能分配一个子串：属于栈顶函数的那个。

Space 分词算法的复杂度

Space complexity of word break algorithm

python

algorithm

time-complexity

space-complexity