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"].

继续熟悉dfs。

class Solution {
public:
    void dfs(string s, int start, vector<string>& re, string &cur_re, unordered_set<string> &dict){
        if(start < 0) return;
        int len = s.length();
        //from back to front
        for(int i = start; i >= 0; --i){
            string sub = s.substr(i, start - i + 1);
            if(dict.find(sub) != dict.end()){
                int len = cur_re.length();
                cur_re.insert(0, " "+sub);
                dfs(s, i - 1, re, cur_re, dict);
                //恢复先前的内容，便于回退
                cur_re = cur_re.substr(cur_re.length() - len);
            }
        }
        if(dict.find(s.substr(0, start + 1)) != dict.end()){
            cur_re.insert(0, s.substr(0, start + 1));
            re.push_back(cur_re);
        }
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> re;
        string cur_re;
        dfs(s, s.length() - 1, re, cur_re, dict);
        return re;
    }
};

Word Break II