单词切割ii

用深度优先搜索，注意优化时间复杂度，否则会超时：

优化后

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        unordered_map<string, vector<string>> mp;
        vector<string> res = dfs(dict, s, mp);
        return res;
    }

    vector<string> dfs(unordered_set<string> &dict, string s,
                       unordered_map<string, vector<string> > &mp) {
        if (s.empty()) return {""};
        if (mp.count(s)) return mp[s];
        vector<string> res;
        for (int i = 1; i <= s.size(); ++i) {
            string word = s.substr(0, i);
            if (!dict.count(word)) continue;
            vector<string> coming = dfs(dict, s.substr(i), mp);
            for (string str : coming) {
                res.push_back(word + (str.empty() ? "" : " ") + str);
            }
        }
        return mp[s] = res;
    }
};

优化前

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        dfs(dict, s, res, vector<string>());
        return res;
    }

    void dfs(unordered_set<string> &dict, string s, vector<string> &res, vector<string> words) {
        if (s.size() < 1) { res.push_back(vec2string(words)); return; }
        for (int i = 1; i <= s.size(); ++i) {
            string sub = s.substr(0, i);
            words.push_back(sub);
            if (dict.find(sub) != dict.end())
                dfs(dict, s.substr(i), res, words);
            words.pop_back();
        }
    }

    string vec2string(vector<string> vec) {
        string s;
        for (int i = 0; i < vec.size(); ++i) {
            s += vec[i];
            if (i != vec.size() - 1) s += " ";
        }
        return s;
    }
};