0
votes

Can someone please help me with the time and space complexity of this code snippet? Please refer 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)
1
Did you try anything yourself? Also, I'd suggest using different code formatting - it's hard to read when you use in-line if but multiline else. - pavel
I feel it's # of word*avg len of word * the entire string or n^2 where n is no of total characters in the string (including duplicates) - curiousD
Ok, searching a substring in string using in operator is sublinear in the best-case and quadratic in the worst-case. Then iterating over keys of dictionary is O(n). Plus there are some comparisons and slicing, but it feels like overall the asymptotic complexity should be O(n^2). - pavel

1 Answers

0
votes
  • 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;