本文共 1314 字，大约阅读时间需要 4 分钟。

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
   
    & re, string &cur_re, unordered_set
    
      &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
     
       wordBreak(string s, unordered_set
      
        &dict) {        vector
       
         re;        string cur_re;        dfs(s, s.length() - 1, re, cur_re, dict);        return re;    }};
       
      
     
    
   

转载地址：http://srlji.baihongyu.com/