这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » word-break-ii

共1条 1/1 1 跳转至

word-break-ii

高工
2018-01-31 13:13:10     打赏

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


思路:

我们从第一个字母开始,遍历字典,看从第一个字母开始能组成哪个在字典里的单词,如果找到了一个,就在这个单词的结束位置的下一个字母处,建立一个列表,记录这个词(保存到一个列表的数组)。当遍历完成这个词典并找出所有以第一个字母开头的词以后,我们进入下一轮搜索。下一轮搜索只在之前找到的词后面位置开始,如果这个位置不是一个词的下一个字母位置,我们跳过,这样我们相当于构建了一个树(实际上是列表数组)。每个找到的词都是这个树的一个分支,有了这个“”树“”,然后我们在用深度优先搜索,把路径加到当中就行。


[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.     void countBreak(string& s, int index, string str,  

  5.                             vector<int>& dp, unorderd_set<string>& dict,   

  6.                             vector<string>& res, int &length)  

  7.     {  

  8.         string substr;  

  9.         for (int len=1; index+len<=length; ++len)  

  10.         {  

  11.             if (dp[index+len] && dict.find(s.substr(index, len))!=dict.end())  

  12.             {  

  13.                 substr = s.substr(index,len);  

  14.                 if (index+len>=length)  

  15.                 {  

  16.                     res.push_back(str+substr);  

  17.                 }  

  18.                 else  

  19.                 {  

  20.                     countBreak(s, index+len, str+substr+" ", dp, dict, res, length);  

  21.                 }  

  22.             }  

  23.         }  

  24.     }  

  25.     vector<string> wordBreak(string s, unordered_set<string>& dict)  

  26.     {  

  27.         int len = s.size();  

  28.         vector<string> res;  

  29.         if (len<1)  

  30.         {  

  31.             return res;  

  32.         }  

  33.   

  34.         vector<int> dp(len+1, 0);  

  35.         dp[0] = 1;  

  36.   

  37.         for (int i=1; i<=len; i++)  

  38.         {  

  39.             for (int j=i-1; j>=0; --j)  

  40.             {  

  41.                 if (dp[j] && dict.find(s.substr(j, i-j)!=dict.end())  

  42.                 {  

  43.                     dp[i] = 1;  

  44.                 }  

  45.             }  

  46.         }  

  47.   

  48.         if (dp[len]==0)  

  49.         {  

  50.             return res;  

  51.         }  

  52.   

  53.         countBreak(s, 0, "", dp, dict, res, len);  

  54.         return res;  

  55.     }  

  56. };  



注意:在backtracking 的时候不用考虑下标超姐的情况,直接将所有到0的都加入结果就行了,因为我们在建这个路径时,就是从0开始建的,不可能越界。




共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]