Time Complexity Analysis for Word Break

Question

What is the time complexity analysis and the space complexity analysis for the following code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s or not dict:
            False

        N=len(s)
        ans=[False for i in range (N+1)]
        ans[0]=True


        for index in range(N):
            if ans[index]:
                for word in wordDict:
                    L=len(word)
                    if index+L <= N and s[index:index+L]==word:
                        ans[index+L]=True

        return ans[-1]

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

amit amit · Accepted Answer · 2020-04-12T19:02:07

Time complexity of this solution is O(n*m*k) - where:

n is the length of the string s.
m is the number of words in wordDict.
k is the average length of a word in wordDict.

Explanation, you repeat n times, for each you check each word in wordDict (m total), and for each such repeat, you read the entire word (of length k).

Space complexity is O(n) - your aux array is independent on the number of words in wordDict or their length, and there is no extra space allocation ¹ depending on the dictionary.

(1) Well, I am not sure how python implements the s[index:index+L], but either way, this is not multipled by n, and never allocated more than once at a time, and never allocared if L > n - so it does not affect space complexity either way.

Time Complexity Analysis for Word Break

1 Answers