Python代码的时间复杂度和空间复杂度

Question

有人能帮我了解一下这个代码片段的时间和空间复杂性吗？请参考leetcode问题-单词中断II。给定一个非空字符串s和一个包含非空单词列表的字典单词dict，在s中添加空格来构造一个句子，其中每个单词都是有效的字典单词。返回所有这些可能的句子。

def wordBreak(self, s, wordDict):
    dp = {}
    def word_break(s):
        if s in dp:
            return dp[s]
        result = []
        for w in wordDict:
            if s[:len(w)] == w:
                if len(w) == len(s):
                    result.append(w)
                else:
                    tmp = word_break(s[len(w):])
                    for t in tmp:
                        result.append(w + " " + t)
        dp[s] = result
        return result
    
    return word_break(s)

Answer 1

>

对于时间复杂性分析，我们几乎总是考虑最坏的情况。

我想O(N^3)运行时和O(N)内存是正确的。

下面是一个细分：

def wordBreak(self, s, wordDict):
    dp = {}
    def word_break(s):
        # This block would be O(N) 
        if s in dp: # order of N
            return dp[s]
        result = []

        # This block would be O(N ^ 2)
        for w in wordDict: # order of N
            if s[:len(w)] == w:
                if len(w) == len(s):
                    result.append(w)
                else:
                    tmp = word_break(s[len(w):])
                    for t in tmp: # order of N
                        result.append(w + " " + t)
        dp[s] = result
        return result
    
    return word_break(s) # This'd be O(N) itself

>

因此，第二个块的O(N^2)乘以调用Word_break(s)的O(N)，最终使其成为O(N^3)。

我们可以将其简化为：

class Solution:
    def wordBreak(self, s, words):
        dp = [False] * len(s)
        for i in range(len(s)): # order of N
            for word in words:  # order of N
                k = i - len(word)
                if word == s[k + 1:i + 1] and (dp[k] or k == -1):  # order of N
                    dp[i] = True
        return dp[-1]

这样会更容易看到：

• 表示i在值域（len(s)):是n的阶；
  • 表示单词中的单词:是n的阶；
    • 如果word==s[k+1:i+1]和(dp[k]或k==-1):是n的阶；