140. Word Break II - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        res = []
        self.backtrack(s, -1, 0, [], 0, res, set(wordDict))
        return res

    def backtrack(self, s, last_idx, cur_idx, cur, cur_len, res, wordDict):
        if cur_idx == len(s):
            if cur_len == len(s): # we advance cur_idx even if no word is picked, so we should validate if all words have been picked
                res.append(' '.join(cur))
            return
        
        cur_word = s[last_idx+1:cur_idx+1]
        if cur_word in wordDict:
            cur.append(cur_word)
            self.backtrack(s, cur_idx, cur_idx+1, cur, cur_len+ len(cur_word), res, wordDict)
            cur.pop()
        self.backtrack(s, last_idx, cur_idx+1, cur, cur_len, res, wordDict)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        wordDict = set(wordDict)
        reachable = [False] * (n+1) # reachable[i] is True if s[i-1] can be reachable
        reachable[0] = True 
        for i in range(n):
            for j in range(i+1, n+1):
                if reachable[i] and s[i:j] in wordDict:
                     reachable[j] = True
        
        res = []
        self.backtrack(s, wordDict, reachable, 0, [], res)
        return res

    def backtrack(self, s, wordDict, reachable, start, path, res):
        if start == len(s):
            res.append(' '.join(path))
            return

        for end in range(start, len(s)):
            if reachable[end+1]:
                word = s[start: end+1]
                if word in wordDict:
                    path.append(word)
                    self.backtrack(s, wordDict, reachable, end+1, path, res)
                    path.pop()

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)
        memo = {}
        return self.backtrack(s, wordDict, 0, memo)

    def backtrack(self, s, wordDict, start, memo):
        if start in memo:
            return memo[start]
        
        if start == len(s):
            return ['']

        res = []
        for end in range(start, len(s)):
            word = s[start: end+1]
            if word in wordDict:
                paths =  self.backtrack(s, wordDict, end+1, memo)
                for path in paths:
                    if path:
                        res.append(word + ' ' + path)
                    else:
                        res.append(word)
        
        memo[start] = res
        return res

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordSet = set(wordDict)
        
        # cache[i] indicates if s[i-1] is reachable
        cache = [False for _ in range(len(s)+1)]
        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
        
        #print(cache)
                    
        output = []
        self.backtrack(s, cache, wordSet, output, [], 0)
        return output
        
    def backtrack(self, s: str, cache: List[str], wordSet: Set[str], output: List[str], cur: List[str], startIdx: int) -> None:
        if startIdx == len(s):
            output.append(' '.join(cur))
            return
        
        for i in range(startIdx, len(s)):
            if cache[i+1]:
                word = s[startIdx: i+1]
                if word in wordSet:
                    cur.append(word)
                    self.backtrack(s, cache, wordSet, output, cur, i+1)
                    cur.pop()

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        int len = s.length();
        if (len == 0) {
            return res;
        }
        
        vector<bool> breakable(len + 1); //breakable[i] is true if s[i .. len - 1] is breakable
        breakable[len] = true;
        for (int i = len - 1; i >= 0; i--) { //O(n ^ 2)
            for (int j = i + 1; j <= len; j++) {
                if (breakable[j]) {
                    string word = s.substr(i, j - i);
                    if (wordDict.find(word) != wordDict.end()) {
                        breakable[i] = true;
                        break;
                    }
                }
            }
        }
        
        string sentence;
        if (breakable[0]) {
            dfs(res, sentence, s, 0, wordDict, breakable);
        }
        return res;
    }
private:
    void dfs(vector<string>& res, string sentence, string& s, int start, unordered_set<string>& wordDict, vector<bool>& breakable) {
        if (start == s.length()) {
            sentence.pop_back();
            res.push_back(sentence);
            return;
        }
        
        for (int i = start + 1; i <= s.length(); i++) {
            if (breakable[i]) { //prune useless dfs
                string word = s.substr(start, i - start);
                if (wordDict.find(word) != wordDict.end()) { //prune useless dfs
                    dfs(res, sentence + word + " ", s, i, wordDict, breakable);
                }
            }
        }
    }
};