Time Complexity and Space Complexity of the Python Code

Question

Can someone please help me with the time and space complexity of this code snippet? Please refer to the leetcode question- Word break ii.Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

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

• For time complexity analysis, almost always we'd take the worst case scenario into account.

• I guess O(N ^ 3) runtime and O(N) memory would be right.

• Here is a breakdown:

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

• Therefore, O(N ^ 2) of the second block is multiplied by O(N) of calling the word_break(s) which would eventually make it O(N ^ 3).

• We can a bit simplify it to:

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]

which would make it easier to see:

• for i in range(len(s)): is an order of N;
  • for word in words: is an order of N;
    • if word == s[k + 1:i + 1] and (dp[k] or k == -1): is an order of N;

Answer 2

Decision Tree

Time Complexity

• height of tree is len(target)=m in worst case
• branching is len(words)=n
• in each recursive call, you make slicing if s[:len(w)]. worst case is m
• T: O(N^m * M)=O(n^m)

Space complexity

• space from call stack is the height of tree=m
• IN each recursive call you are making suffix and storing it. its length is m
• S : O(m*m)