139. Word Break

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, determine ifscan be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s="leetcode",
dict=["leet", "code"].

Return true because"leetcode"can be segmented as"leet code".

S: 区间型Dp O(N^N)

valid[i]表示s从0到i - 1可被拆分为dict中的词语，对 k < i，只要valid[k]且s.substr(k, i - k)是dict中的词语

    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        if (wordDict.size() == 0 || n < 1) {
            return false;
        }
        unordered_set<string> dict;
        for (string s : wordDict) {
            dict.insert(s);
        }
        vector<bool> valid(n + 1, false);
        valid[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (valid[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    valid[i] = true;
                    break;
                } 
            }
        }
        return valid[n];
    }

140. Word Break II

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s="catsanddog",
dict=["cat", "cats", "and", "sand", "dog"].

A solution is["cats and dog", "cat sand dog"].

S1: 记忆化搜索

dp[string]存储该段string的所有可能break, 由大到小，只有在该string可拆分时才进行搜索

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {             
        for (string str : wordDict) dict.insert(str);         
        int n = s.size();     
        return dfs(s);       
    }
    vector<string> dfs(string s) {
        if (dp.find(s) != dp.end()) return dp[s];
        vector<string> result;
        if (dict.find(s) != dict.end()) result.push_back(s);
        int n = s.size();
        for (int i = 1; i < n; ++i) {
            string word = s.substr(i);
            if (dict.find(word) != dict.end()) {
                vector<string> words = appendWord(dfs(s.substr(0, i)), word);
                result.insert(result.end(), words.begin(), words.end());
            }
        }
        dp[s] = result;
        return result;
    }

     vector<string> appendWord(vector<string> pre, string word) {
         for (string& s : pre) s += " " + word;
         return pre;
     }

private:
    unordered_map<string, vector<string>> dp;
    unordered_set<string> dict;
};

S2： DP

dp[i]存储0 - i-1位可分解的所有可能，思路和Word break I一样, 由小到大

//会超时
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;     
        for (string str : wordDict) dict.insert(str);  
        unordered_map<int, vector<string>> breakmap;
        int n = s.size();
        breakmap[0] = vector<string>{""};

        for (int i = 1; i <= n; ++i) {
            vector<string> sentence;
            for (int j = 0; j < i; ++j) {
                string str = s.substr(j, i - j);
                if (breakmap[j].size() > 0 && dict.find(str) != dict.end()) {
                    for (string word : breakmap[j]) {
                        if (word.size() > 0) word += " ";
                        sentence.push_back(word + str);
                    }
                }
            }
            breakmap[i] = sentence;
        }
        return breakmap[n];
    }