依然是宽度优先搜索,这个题需要用dp判断下是否可解。我也是看别人的博客才知道,不然一直TLE。
class Solution { public: bool **map; set&lt;int&gt;wordlens; vector&lt;string&gt;result; vector&lt;string&gt; wordBreak(string s, unordered_set&lt;string&gt; &amp;dict) { wordlens.clear(); unordered_set&lt;string&gt;::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 &lt; s.length();i++) { map[i] = new bool[s.length()]; for(int j = 0;j &lt; s.length();j++) { map[i][j] = false; } } for(int start = 0;start &lt; s.length();start++) { for(int len = 1;len &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 &lt; s.length();i++) { for(int j = 0;j &lt;= i;j++) { for(int k = j;k &lt; i;k++) { if(map[j][k] &amp;&amp; map[k+1][i])map[j][i] = true; } } } //for(int i = 0;i &lt; s.length();i++) { // for(int j = 0;j &lt; s.length();j++) { // cout &lt;&lt; map[i][j] &lt;&lt; ' '; // } // cout &lt;&lt; endl; //} if(map[0][s.length()-1] == false)return result; string item = &quot;&quot;; findSen(s,0,dict,item); return result; } private: void findSen(string &amp;s,int start,unordered_set&lt;string&gt;&amp;dict,string &amp;item) { if(start &gt;= s.length()) { result.push_back(item); return ; } set&lt;int&gt;::iterator it; for(it = wordlens.begin();it != wordlens.end();it++) { int len = *it; if(start + len &gt; s.length()) return; string tmp = string(s,start,len); if(dict.find(tmp) != dict.end()) { string itembp = item; if(start != 0)item += &quot; &quot;; item += tmp; findSen(s,start+len,dict,item); item = itembp; } } } };