首页 > 代码库 > Word Break
Word Break
这个题目思路:在一个bool型数组中,像接力一样传递匹配成功,传递到最后一个字符,说明匹配成功。说的明白点就是从第i(0~n)个字符开始向后与子串进行匹配,匹配的数组中标记为true,循环比较。
需要注意的是:unordered_set的count(T s)查看是否包含该元素。string类的substr(pos,n)函数返回从pos位置开始的n个字符。
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string> &dict) { 4 int MainLen = s.size(); 5 vector<bool> dp(MainLen,false); 6 dp[0] = true; 7 for(int i=0;i<MainLen;i++) 8 { 9 if(dp[i])10 {11 for(int j = i;j<MainLen;j++)12 {13 if(dict.count(s.substr(i,j-i+1)))14 {15 dp[j+1] = true;16 }17 }18 }19 }20 return dp[MainLen];21 }22 };
Word Break
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。