[LeetCode] 139. Word Break

Problem : https://leetcode.com/problems/word-break/

Iterate the input string from left to right. Find word in dictionary. If found, break the input string into 2 parts, check if the 2nd part is also constructed by the words in dictionary.

Time Complexity = O ( N )

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        @lru_cache(maxsize=None)
        def dfs(start):
            if start >= len(s): 
                return True
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet and dfs(i+1):
                    return True
                    
            return False
        
        return dfs(0)

BFS solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        queue = deque([0])
        visited = set([0])
        
        while queue:
            start = queue.popleft()
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet:
                    if i + 1 == len(s):
                        return True

                    if i + 1 not in visited:
                        visited.add(i+1)
                        queue.append(i+1)
        
        return False

The bottom-up solution:

class Solution {

    public boolean wordBreak(String s, List wordDict) {
        HashSet<String> words = new HashSet();
        int wordLen = 0;
            
        for (int i = 0; i < wordDict.size(); i++) {
            words.add(wordDict.get(i));
            wordLen = Math.max(wordLen, wordDict.get(i).length());
        }
        
        int N = s.length();
        boolean[] dp = new boolean[N];
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = i; i - j + 1 <= wordLen && j >= 0; j--) {
                
                if (words.contains(s.substring(j, i+1)) && (i + 1 == N || dp[i+1]) ) {
                    dp[j] = true;
                }
            }
        }
        
        return dp[0];

    }
}

Edited on 11/26/2021. Add the bottom-up solution.