sol.cpp

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        root = new TrieNode();
        
        for (string word : wordDict) {
            root->insert(word, 0);
        }
        
        return wordBreakHelper(s, 0);
    }
    
    vector<string> wordBreakHelper(const string& s, int i) {
        if (sol[i]) {
            return mem[i];
        }
        
        vector<string> res;
        
        if (i >= s.size()) {
            return res;
        }
        
        TrieNode* prev = root;
        string curWord = "";
        for (int j = i; j < s.size(); j++) {
            curWord += s[j];
            TrieNode* cur = prev->search(curWord, curWord.size()-1); // Search from last found char ;)
            
            if (cur != NULL && cur->endOfWord) {
                vector<string> perm = wordBreakHelper(s, j+1);
                
                if (perm.size() == 0 && j+1 >= s.size()) {
                    res.push_back(curWord);
                } else {
                    for (string w : perm) {
                        res.push_back(curWord + " " + w);
                    }
                }
            } else if (cur == NULL) {
                sol[i] = true;
                return (mem[i] = res);
            }
            
            prev = cur;
        }
        
        sol[i] = true;
        return (mem[i] = res);
    }
    
private:
    TrieNode* root;
    bool sol[5001];
    map<int, vector<string>> mem;
};