LeetCode 140. Word Break II [Hard] [C++] 解題筆記

 這題是 139. Word Break 的進階題，一樣給定一個 string s 和字串陣列 wordDict，但這題要求的是所有可能的解，即由 wordDict 中的字串組合成 s 的所有可能方式(wordDict 中的字串可以重複使用)。

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

想法:

    這題可以採取遞迴加上 memorize 的方式來列舉所有可能，如 139. Word Break 一樣將 s 分割為兩部份來討論，

確定右半部在 wordDict 中之後便可遞迴列舉左半部所有可能的分割方式，列舉完左半部分割方式之後便可以將之與剛剛確定的

右半部部份結合形成一種組合出 s 的方式。

例如: s = catsanddog => catsand dog

只有將 dog 作為右半部份這一種分割方式，而 catsand 經過遞迴列舉之後可以得到 cat sand 和 cats and 兩種分割方式，

因此最後合併就得到 "cats and dog" 與 "cat sand dog" 兩個解。

完整程式碼:

/* DFS with memerize, O(2^n) time, O(2^n) space */
class Solution {
public:
    vector<string> enumerate(const vector<string>& prefixes, const string& word) {
        vector<string> res;
        for (const auto& prefix : prefixes) {
            res.push_back(prefix + " " + word);
        }
        return res;
    }
    const vector<string>& wordBreak(string s, unordered_set<string>& dict) {
        if (mem.count(s)) { return mem[s]; }
        // ans for substr s
        vector<string> ans;
        
        // s in dict, add it into ans
        if (dict.count(s)) {
            ans.push_back(s);
        }
        for (int i = 1; i < s.size(); i++) {
            // check whether the right part is in dict
            const string& right = s.substr(i);
            if (!dict.count(right)) { continue; }
            
            // get all combination of left part
            const string& left = s.substr(0, i);
            const vector<string> left_solution = enumerate(wordBreak(left, dict), right);
            ans.insert(ans.end(), left_solution.begin(), left_solution.end());
        }
        // vector.swap is O(1) operation (just exchange reference to their data)
        mem[s].swap(ans);
        return mem[s];
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return wordBreak(s, dict);
    }
private: 
    // record ans for every substr
    unordered_map<string, vector<string>> mem;
};