class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if (m.count(s)) return m[s];	//判断map中有没有s
        if (s.empty())  return {""};
        vector<string> res;
        for (string word : wordDict) {	
            if (s.substr(0, word.size()) != word) continue;	//进行前缀判断
            for (string r : wordBreak(s.substr(word.size()), wordDict)) {	
            //DFS搜索 返回值为当前前缀对应的解 被分割好了
            	//sustr去除前缀
                res.push_back(word + (r.empty() ? "" : " ") + r);	
                //整合答案
            }
        }
        return m[s] = res;
    }
private:
    unordered_map<string, vector<string>> m;
};