140. Word Break II

https://leetcode.com/problems/word-break-ii/description/

找dict中所有能拼成S的组合。找所有，DFS。遍历所有可能的划分，并用map记录下每个可能的s的答案以复用。

/*
 * @lc app=leetcode id=140 lang=cpp
 *
 * [140] Word Break II
 */

// @lc code=start
class Solution {
    unordered_map<string, vector<string>> m;
public:
    vector<string> dfs(string s, unordered_set<string> &words) {
        if (m.count(s)) return m[s];
        vector<string> res;
        for (int i = 0; i < s.length() - 1; ++i) {
            const auto b = s.substr(i + 1);
            if (!words.count(b)) continue;
            auto l = dfs(s.substr(0, i + 1), words);
            if (!l.empty()) {
                for (const auto a : l) {
                    res.push_back(a + " " + b);
                }
            }
        }
        if (words.count(s)) res.push_back(s);
        m[s] = res;
        return res;
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());
        return dfs(s, words);
    }
};
// @lc code=end