139. Word Break

Solution 1: DFS (TLE)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        def dfs(s, wordSet):
            if not s:
                return True
            
            for idx in range(len(s)):
                if (s[: idx + 1] in wordSet) and dfs(s[idx + 1: ], wordSet):
                    return True
            return False
            
        wordSet = set()
        for word in wordDict:
            wordSet.add(word)
        ans = dfs(s, wordSet)
        return ans

Time Complexity: O(2^N)
Space Complexity: O(N) // Recursive call stack of tree height O(N)

Solution 2: DP

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # (dp) isStrToIdxValidWB[i] is True if there is a word in the wordDict that ends at (i - 1)th index of s, [0] is True by default
        n = len(s)
        isStrToIdxValidWB = [True] + [False] * n
        for idx in range(1, n + 1):
            for word in wordDict:
                startIdxOfWord = idx - len(word)
                # 1. string of 0 to (startIdxOfWord - 1) is valid word break
                # 2. string (word) of startIdxOfWord to idx match the word in wordDict
                if (isStrToIdxValidWB[startIdxOfWord]) and s[startIdxOfWord: idx] == word:
                    isStrToIdxValidWB[idx] = True
        return isStrToIdxValidWB[n]

Time Complexity: O(N^2*M) // String loop (N) + word loop (M) + slicing & comparison (takes N time each), N = len(s) and M = len(wordDict)
Space Complexity: O(N)

Solution 3: DP - 2

Time Complexity: O(N^2)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/word-break/discuss/169383/solved-The-Time-Complexity-of-The-Brute-Force-Method-Should-Be-O(2n)-and-Prove-It-Below
https://leetcode.com/problems/word-break/discuss/43808/Simple-DP-solution-in-Python-with-description
https://leetcode.com/problems/word-break/discuss/43788/4-lines-in-Python