**LeetCode—Word Break

http://blog.csdn.net/xietingcandice/article/details/43705383

Given a string s and a dictionary of words dict, determine ifs can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

在这个例子当中,主要是为了看一个句子字符串中的词语能不能够都划分为词典中的词语

flag[j]为true,那么就是要求存在一个变量k,能够满足flag[k]为ture,同时substr(k,j-k)是在字典当中的

但是在这个例子当中是不关心最终的划分方式

[cpp] view plaincopyprint?

  1. class Solution {    
  2. public:    
  3. bool wordBreak(string s, unordered_set<string> &dict) {    
  4. int length = s.size();  
  5. vector<bool> val(length+1,false);  
  6. val[0] = true; //<根据长度进行设置
  7. int i = 0;  
  8. int j = 0;  
  9. for(i = 0; i < length; i++)  
  10. {  
  11. if(val[i])//<前一个长度是可以进行分解的
  12.     {  
  13. for(j = 1; (i+j) <= length; j++)  
  14.         {  
  15.             string tmp = s.substr(i,j);  
  16. if(dict.count(tmp) > 0)  
  17.             {  
  18.                 val[i+j] = true;  
  19.             }  
  20.         }  
  21.     }  
  22. }  
  23. return val[length];  
  24.        }    
  25.    };    

对应着有第二个例子:

Word Break II

Given a string s and a dictionary of words dict, add spaces ins 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"].

在这个例子当中,主要是需要将分解的结果放在一个vector的结构体当中

有一种方法是DFS 方法,还没有研究

这里主要还是借鉴了第一个例子当中的方法,先检测是否能够被划分,如果可以被划分,之后再通过遍历进行存储

[cpp] view plaincopyprint?

  1. class Solution {  
  2. public:  
  3. void breakWord(vector<string> &res, string &s, unordered_set<string> &dict, string str, int idx, vector<bool> &dp) {  
  4.         string substr;  
  5. for (int len = 1; idx + len <= s.length(); ++len) {  
  6. if (dp[idx + len] && dict.count(s.substr(idx,len)) > 0) {  
  7.                 substr = s.substr(idx, len);  
  8. if (idx + len < s.length()) {  
  9.                     breakWord(res, s, dict, str + substr + " ", idx + len, dp);  
  10.                 } else {  
  11.                     res.push_back(str + substr);  
  12. return;  
  13.                 }  
  14.             }  
  15.         }  
  16.     }  
  17.     vector<string> wordBreak(string s, unordered_set<string> &dict) {  
  18.         vector<bool> dp(s.length() + 1, false);  
  19.         dp[0] = true;  
  20. for (int i = 0; i < s.length(); ++i) {  
  21. if (dp[i]) {  
  22. for (int len = 1; i + len <= s.length(); ++len) {  
  23. if (dict.count(s.substr(i, len)) > 0) {  
  24.                         dp[i + len] = true;  
  25.                     }  
  26.                 }  
  27.             }  
  28.         }  
  29.         vector<string> res;  
  30. if (dp[s.length()])   
  31.             breakWord(res, s, dict, "", 0, dp);  
  32. return res;  
  33.     }  
  34. };  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏儿童编程

一张思维导图看懂《周易》基础要点——参考《易经杂说》

本图对《易经》的基础部分做了归纳总结。主要参考南怀瑾先生的《易经杂说》及不同版本《周易》。

82540
来自专栏儿童编程

声音功能让儿童编程更有创造性

导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

13540
来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

13810
来自专栏儿童编程

《动物魔法学校》儿童学编程Scratch之“外观”部分

导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

18640
来自专栏儿童编程

一张导图梳理欧洲简史梗概

3.1K30
来自专栏儿童编程

天干地支五行八卦的对应关系

18790
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

30840
来自专栏儿童编程

什么样的人生才是有意义的人生——没有标准的标准答案

【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

1.7K50
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

21770
来自专栏儿童编程

儿童编程Scratch之“画笔”基础功能学习总结

Scratch中“画笔”功能能够让使用者模拟画笔在舞台上创作,合理运用能够给作品带来极大的趣味性。

65020

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励