依然是宽度优先搜索，这个题需要用dp判断下是否可解。我也是看别人的博客才知道，不然一直TLE。

class Solution {
public:
    bool **map;
    set<int>wordlens;
    vector<string>result;
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        wordlens.clear();
        unordered_set<string>::iterator it;
        for(it = dict.begin();it != dict.end();it++) {
            string itstr = <em>it;
            wordlens.insert(itstr.length());
        }
        result.clear();
        map = new bool</em>[s.length()];
        for(int i = 0;i &amp;lt; s.length();i++) {
            map[i] = new bool[s.length()];
            for(int j = 0;j &amp;lt; s.length();j++) {
                map[i][j] = false;
            }
        }
        for(int start = 0;start &amp;lt; s.length();start++) {
            for(int len = 1;len &amp;lt;= s.length() - start;len++) {
                string tmp = s.substr(start,len);
                if(dict.find(tmp) != dict.end()) {
                    map[start][start+len-1] = true;
                }
            }
        }
        for(int i = 0;i &amp;lt; s.length();i++) {
            for(int j = 0;j &amp;lt;= i;j++) {
                for(int k = j;k &amp;lt; i;k++) {
                    if(map[j][k] &amp;amp;&amp;amp; map[k+1][i])map[j][i] = true;
                }
            }
        }
        //for(int i = 0;i &amp;lt; s.length();i++) {
        //  for(int j = 0;j &amp;lt; s.length();j++) {
        //      cout &amp;lt;&amp;lt; map[i][j] &amp;lt;&amp;lt; ' ';
        //  }
        //  cout &amp;lt;&amp;lt; endl;
        //}
        if(map[0][s.length()-1] == false)return result;
        string item = &amp;quot;&amp;quot;;
        findSen(s,0,dict,item);
        return result;
    }
private:
    void findSen(string &amp;amp;s,int start,unordered_set&amp;lt;string&amp;gt;&amp;amp;dict,string &amp;amp;item) {
        if(start &amp;gt;= s.length()) {
            result.push_back(item);
            return ;
        }
        set&amp;lt;int&amp;gt;::iterator it;
        for(it = wordlens.begin();it != wordlens.end();it++) {
            int len = *it;
            if(start + len &amp;gt; s.length())
                return;
            string tmp = string(s,start,len);
            if(dict.find(tmp) != dict.end()) {
                string itembp = item;
                if(start != 0)item += &amp;quot; &amp;quot;;
                item += tmp;
                findSen(s,start+len,dict,item);
                item = itembp;
            }
        }
    }
};