首页 > 代码库 > Word Break (14)
Word Break (14)
Given a string s and a dictionary of words dict, determine if s 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".
这一题是一题简单的动态规划。设bool ok[s.len+1],ok[i]的含义是长度为i的字符串是否能被字典中的单词所匹配。设ok[0]=true,即长度为0的字符串设置为能被匹配。很容易写出最优子结构。如下，有：
ok[i]= true (i=0)
ok[j]&&(dict能否找到由s[j...i-1]的匹配的单词) （ j由i-1到0，有一个为true 就break）
其思想是用ok[i]记录长度为i的字符串s[0...i]是否能被字典匹配，对于更长的字符串，如果该字符串能分为两部分，前半部分已经可以匹配了，剩下的后半部分在字典里有匹配项，则该更长的字符串也能被匹配。
上代码：
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string> &dict) { 4 int len=s.length(); 5 int i,j; 6 bool *ok=new bool[len+1]; 7 memset(ok,false,(len+1)*sizeof(bool));//这里不能为sizeof(ok),否则会wrong 8 ok[0]=true; 9 for(i=1;i<=len;i++){10 for(j=i-1;j>=0;j--){11 if(ok[j]&&dict.find(s.substr(j,i-j))!=dict.end())12 {13 ok[i]=true;14 break;15 }16 }17 }18 return ok[len];19 }20 };
贴出一段简单的代码及其运行结果！貌似腾讯实习生笔试出过这题，但是一直不知道为什么。上文中的错误就在此处，ps:因为这个原因找了好长时间都没找到错误。
1 #include<iostream>2 3 using namespace std;4 5 int main(){6 bool *ok=new bool [100];7 cout<<sizeof(ok);//结果是48 }
Word Break (14)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。