140. Word Break II

记忆化搜索 memo+dfs O(n²2ⁿ) time O(2ⁿn+W) space
worst case是每个prefix都能在字典里找着，比如[‘a’, ‘aa’, ‘aaa’, …]这种，每个长度为i的suffix可能有2^{i - 1}个组成方法，每次递归需要O(n)，递归深度为O(n)，所以总复杂度为O(n*n*2ⁿ)
这道题不需要用trie，太麻烦！
因为字符串没法简单的做backtracking所以采用后缀式搜索来避免
cache的时候用下标做key即可

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> d(wordDict.begin(), wordDict.end());
        return dfs(s, 0, d);
    }

    vector<string> dfs(const string &s, int b, const unordered_set<string> &d) {
        if (cache.count(b)) return cache[b];
        int n = s.length();
        if (b == n) return {""}; // 切记要返回一个空串不能是空集！！
        string w;
        for (int i = b; i < n; ++i) {
            w += s[i];
            if (d.count(w)) {
                for (const auto &suffix : dfs(s, i + 1, d)) {
                    cache[b].push_back(suffix.empty() ? w : w + ' ' + suffix); // 注意suffix有可能是空串！！
                }
            }
        }
        return cache[b];
    }

    unordered_map<int, vector<string>> cache;
};