LC139. Word Break

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        """
        main idea: Bottom up -  put l, le, lee, leet into cache, and look up the dictionary to find if any word match 
        dp[i] for substring s from idex 0 to index i-1, there is a word in wordDict
        tc O(N*len(wordDict)*W) sc O(N)  
        """
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(1,n+1):
            for j in range(i):
                if dp[j] != False and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[n]

for this kind of problem, which time complexity is [length of s][size of dict][avg length of words in dict]. We can usually remove [size of dict] by using Tire, remove [avg length of words in dict] by KMP, and what’s more, remove both [size of dict] and [avg length of words in dict] by AC-automata. And of course these are all doable for this problem.

optimization time complexity: [length of s][size of dict][avg length of words in dict]

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        #tc O(N*len(wordDict)*W) sc O(N)  
        n = len(s)
        wordDict = set(wordDict)
        dp = [False] * (n+1)
        dp[0] = True 
        for i in range(1,n+1):
            for w in wordDict:
                w_len = len(w)
                if w_len <= i and dp[i-w_len] and s[i-w_len:i] == w:
                    dp[i] = True
                    break
        return dp[n]

Top Down solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = {}
        word_set = set(wordDict)
        return self.helper(s,0,word_set,memo)
    
    def helper(self, s, start, word_set, memo):
        if start in memo:
            return memo[start]
        if start == len(s):
            return True 
        for end in range(start+1, len(s)+1):
            if s[start:end] in word_set and self.helper(s,end,word_set, memo):
                memo[start] = True
                return memo[start]
        memo[start] = False 
        return memo[start]

BFS solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        """ tc O(N^3) sc O(N)
        """
        word_set = set(wordDict)
        start = 0
        n = len(s)
        seen = set()
        q = collections.deque([start])
        while q:
            cur = q.popleft()
            if cur in seen:
                continue 
            for end in range(cur+1,n+1):
                if s[cur:end] in word_set:
                    q.append(end)
                    if end == n:
                        return True 
                seen.add(cur)
        return False 