LeetCode: Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Use iteration to find the prev node in the path of final solution, and use backtracking to recover the solution. We can also use iteration to directly compute the solution, but would cost much more space as a lot of redundant strings on the path.

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<vector<int>> prevs(s.length()+1);
        vector<bool> checked(s.length()+1, false);
        checked[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (checked[j] && dict.find(s.substr(j,i-j)) != dict.end()) {
                    if (!checked[i]) {
                        checked[i] = true;
                    }
                    prevs[i].push_back(j);
                }
            }
        }
        vector<string> res;
        backtracking(s, prevs, res, s.length());
        return res;
    }
    void backtracking(const string &s, const vector<vector<int>> &prevs, vector<string> &res, int index) {
        for (int i = 0; i < prevs[index].size(); ++i) {
            if (prevs[index][i] == 0) {
                res.push_back(s.substr(0, index));
            } else {
                backtracking(s, prevs, res, prevs[index][i]);
                for (int j = 0; j < res.size(); ++j) {
                    string temp = res[j];
                    temp.erase(remove( temp.begin(), temp.end(), ' '), temp.end());
                    if(temp.length() == prevs[index][i]){
                        res[j] += " " + s.substr(prevs[index][i], index-prevs[index][i]);
                    }
                }   
            }
        }
    }
};