140

class Solution {
public:
    unordered_map<int, vector<string>> memo;
    unordered_map<string, bool> wordDict;
    vector<string> wordBreak(string s, vector<string>& dict) {
        memo[s.size()].push_back("");
        for(auto word: dict)
            wordDict[word] = true;
        return solve(0, s);
    }

    vector<string> solve(int i, string &s){
        if(memo.count(i)) return memo[i];
        for(int j=i+1; j<=s.length(); j++){
            string word = s.substr(i, j-i);
            if(wordDict.count(word)){
                for(string str: solve(j, s)){
                    memo[i].push_back(word+(str == "" ? "" : ' '+str));
                }
            }
        }
        return memo[i];
    }

};