140. Word Break II

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        unordered_map<int, vector<string>> memo;
        for (string word : wordDict) dict.insert(word);
        return helper(s, 0, memo, dict);
    }
private:
    vector<string> helper(string s, int pos, 
                          unordered_map<int, vector<string>>& memo, unordered_set<string>& dict) {
                            //   cout<<s<<' '<<pos<<endl;
        if (!memo.count(pos)) {
            for (int i = pos; i < s.size(); i++) {
                string pre = s.substr(pos, i - pos + 1);
            // cout<<pre<<endl;
                if (dict.count(pre)) {
                    string sur = s.substr(i + 1, s.size() - i - 1);
            // cout<<pre<<' '<<sur<<endl;
                    if (sur == "") {
                        memo[pos].push_back(pre);
                        continue;
                    }
                    vector<string> surbrokens = helper(s, i + 1, memo, dict);
                    for (string surbroken : surbrokens)
                        memo[pos].push_back(pre + " " + surbroken);
                }
            }
        }
        return memo[pos];
    }
};