首页 > 代码库 > Word Break II
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"].
思路：从后往前遍历string，使用Q[i]记录从输入string第i+1个元素开始的所有合法的子sentence序列（即能顺利达到string结尾）。Q[0]即为最终所求。
求解Q[i]时，依次访问Q[k]( k = i+1, i+2, ..., len-1 )，若Q[k]非空且s.substr(i,k-i)是合法的单词，说明从Q[i]经过Q[k]能达到string尾部，其过渡单词为s.substr(i,k-i)。于是，我们将s.substr(i,k-i)与Q[k]每一个元素拼接起来，并存入Q[i]。循环直至Q[0]求解完毕。
1 class Solution { 2 public: 3 vector<string> wordBreak( string s, unordered_set<string> &dict ) { 4 // initialise. 5 string str = ""; int size = s.length(); 6 vector<string>* Q = new vector<string>[size]; 7 // process each character from backward. 8 for( int i = size-1; i >= 0; --i ) { 9 for( int len = i+1; len <= size; ++len ) {10 str = s.substr( i, len-i );11 if( dict.find( str ) != dict.end() ) {12 if( len != size ) {13 for( size_t k = 0; k != Q[len].size(); ++k ) {14 Q[i].push_back( str + " " + Q[len][k] );15 }16 }17 else {18 Q[i].push_back( str );19 }20 }21 }22 }23 return Q[0];24 }25 };
下面的算法与上面的算法类似，不同之处在于Q[i]只保存了所有以s[i]开头的合法的单词。然后，通过递归求解出完整的sentence路径。
1 class Solution { 2 public: 3 vector<string> wordBreak( string s, unordered_set<string> &dict ) { 4 if( s.empty() || dict.empty() ) { return vector<string>(0); } 5 int sLen = s.length(); 6 vector<string> *Q = new vector<string>[sLen]; 7 for( int i = sLen-1; i >= 0; --i ) { 8 string subStr = s.substr( i, sLen-i ); 9 if( dict.find( subStr ) != dict.end() ) { Q[i].push_back( subStr ); }10 for( int j = i+1; j < sLen; ++j ) {11 subStr = s.substr( i, j-i );12 if( !Q[j].empty() && dict.find( subStr ) != dict.end() ) { Q[i].push_back( subStr ); }13 }14 }15 string sentence = "";16 GenerateSentences( Q, sLen, sentence );17 delete [] Q;18 return sentences;19 }20 private:21 void GenerateSentences( vector<string> *Q, int size, string &sentence ) {22 if( size <= 0 ) { sentences.push_back( sentence ); return; }23 for( auto iter = Q[0].begin(); iter != Q[0].end(); ++iter ) {24 if( sentence.empty() ) {25 GenerateSentences( Q+(int)(*iter).length(), size-(int)(*iter).length(), *iter );26 } else {27 string tmp = sentence + " " + *iter;28 GenerateSentences( Q+(int)(*iter).length(), size-(int)(*iter).length(), tmp );29 }30 }31 return;32 }33 vector<string> sentences;34 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。