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

题意：
给定一个字符串和一个单词字典，找出可以用字典里的单词来分割这个字符串的各种组合。
思路：dfs
void dfs(int start, string partition);
start表示当前要分割的字符串s[start:]，
设 k将 s分割为s[:k]和s[k:]，则 0 < k <= s.size() 且 s[:k]存在字典dict中
按上面这样的思路直接做会超时，可采用dfs + 剪枝的思路
增加一个bool数组 possible[k] 表示字符串s[k:]是否可用字典里的单词来分割

unordered_set
  
    _dict;
vector
   
     res; vector
    
      possible; string _s; void dfs(int start, string partition){ if(start >= _s.size()){ res.push_back(partition.substr(1, partition.size() - 1)); return; } for(int k = start + 1; k <= _s.size(); ++k){ if(possible[k] && _dict.find(_s.substr(start, k - start)) != _dict.end()){ //剪枝 int size_before = res.size(); dfs(k , partition + " " + _s.substr(start, k - start)); if(res.size() == size_before) possible[k] = false; //剪枝 } } } vector
     
       wordBreak(string s, unordered_set
      
        &dict){ _dict = dict; _s = s; possible = vector
       
        (s.size() + 1, true); dfs(0, ""); return res; }