139. Word Break - cocoder39/coco39_LC GitHub Wiki

139. Word Break

Notes 2022

time complexity O(L^3) where L is length of each word

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        
        cache = [None for _ in range(len(s)+1)] # cache[i] indicates whether s[i-1] is reachable
        cache[0] = True
        
        for i in range(len(s)+1):
            for j in range(i+1, len(s)+1):
                if cache[i] and s[i:j] in wordSet:
                    cache[j] = True
        
        return cache[len(s)]

============================================================================

use dp to solve "valid" problem. we need dp[len] to determine if s is valid. Thus dp[i] = true if s[0 .. i - 1] is valid.

the worst case time complexity is O(n ^ 3) rather than O(n ^ 2) when considering substr(). for each i, t(i) = 1 + 2 .. i = O(i^2), thus total time is O(n^3)

bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.length();
        if(len == 0){
            return false;
        }
        vector<bool> inDict(len + 1); //inDict[i] is true iff s[0 .. i - 1] is in dict
        
        inDict[0] = true; 
        for(int i = 1; i <= len; i++){ //check s[0 .. i - 1] 
            for(int j = i - 1; j >= 0; j--){
                if(inDict[j]){ // s[0 .. j - 1] is in dict
                    string word = s.substr(j, i - j);
                    if(wordDict.find(word) != wordDict.end()){
                        inDict[i] = true;
                        break;
                    }
                }
            }
        }
        return inDict[len];
    }

an optimization is restrict the length of the word to be checked within [minLength, maxLength] of words in dict

bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.length();
        if (len == 0) {
            return false;
        }
        
        int low = len, high = 0;
        for (auto& word : wordDict) {
            int l = word.length();
            low = min(low, l);
            high = max(high, l);
        }

        vector<bool> dp(len + 1); //dp[i] = true if s[0 .. i-1] is a word in dict
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = i - low; i - j <= high && j >= 0; j--) {
                if (dp[j]) {
                    string word = s.substr(j, i - j);
                    if (wordDict.find(word) != wordDict.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[len];
    }

recursion: t(n) = t(n-1) + t(n-2) + ... = 2t(n-1) = O(2^n)

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if (s.empty()) {
            return false;
        } 
        return helper(s, 0, wordDict);
    }
private:
    bool helper(string& s, int start, unordered_set<string>& wordDict) {
        if (start == s.length()) {
            return true;
        }
        for (int i = start; i < s.length(); i++) {
            string word = s.substr(start, i - start + 1);
            if (wordDict.find(word) != wordDict.end()) {
                if (helper(s, i + 1, wordDict)) return true;
            }
        }
        return false;
    }
};
⚠️ **GitHub.com Fallback** ⚠️