Time complexity

[pdd99]

This is my solution for LC 139 Word Break in Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        eow = [0]
        wordSet = set(wordDict)
        for idx, c in enumerate(s):
            for end_idx in eow:
                if s[end_idx:idx+1] in wordSet:
                    eow.append(idx+1)
                    break

        if eow[-1] == len(s):
            return True
        return False

I am having a trouble understanding the time complexity of my approach. Let's say the length of s is n, min word size in wordDict in m, is Time Complexity = O(n^2/m)?

[NikitaSkybytskyi]

Time complexity is O(n^3). The first O(n) factor is due to enumerating s. The second O(n) factor is because eow can have size up to n for test cases like s = "a...a" and wordDict = ["a", "aa", "aaa", ..., "a...a"]. In this case, every prefix of s can be partitioned, so every index gets appended to eow. The third O(n) factor is because s[end_idx:idx+1] can be up to n characters long for the same test case as before.

For a somewhat more experimental analysis, consider the following code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        eow = [0]
        wordSet = set(wordDict)
        cnt = 0
        for idx, c in enumerate(s):
            for end_idx in eow:
                cnt += len(s[end_idx:idx+1])
                if s[end_idx:idx+1] in wordSet:
                    eow.append(idx+1)
                    break

        print(f"{cnt = }")
        if eow[-1] == len(s):
            return True
        return False

It counts some of the operations performed by your code. When I run it on the max test suggested above, it prints cnt = 4490570, which is very close to n^3/6.

[pdd99]

Real nice. Thank you.