word_break2.cc

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<vector<int> > path(s.size(), vector<int>());
        vector<string> result;
        vector<bool> word_map(s.size() + 1, false);
        word_map[0] = true;
        
        if (!s.size()) {
            return result;
        }
        
        for (int i = 0; i < s.size() + 1; i++) {
            if (word_map[i]) {
                for (int j = i + 1; j < s.size() + 1; j++) {
                    if (dict.find(s.substr(i, j - i)) != dict.end()) {
                        word_map[j] = true;
                        path[j-1].push_back(i);
                    }
                }
            }
        }
        
        vector<string> sentence;
        dfs(s.size() - 1, s, sentence, path, result);
        return result;
        
    }
    
    void dfs(int offset, string &s, vector<string> &sentence, vector<vector<int> > &path, vector<string> &result) {
        if (offset == -1) {
            string str;
            for (int i = 0; i < sentence.size(); i++) {
                str = str + sentence[sentence.size() - i - 1] + " ";
            }
            str.pop_back();
            result.push_back(str);
            return;
        }
        
        if (path[offset].size()) {
            for (int j = 0; j < path[offset].size(); j++) {
                sentence.push_back(s.substr(path[offset][j], offset - path[offset][j] + 1));
                dfs(path[offset][j] - 1, s, sentence, path, result);
                sentence.pop_back();
            }
        }
    }
};