首页 > 代码库 > leetcode[139] Word Break
leetcode[139] Word Break
给一个字符串，判断是否能够分为若干个部分，并且每个部分都能在字典dict里面找到。有的话就返回true。例如：
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
思路：利用动态规划，一开始初始化的时候数组dp[]存的是每个位置到终点的词是否在词典里。如果是存true。
然后从后往前，判断当前的dp[i]是否为true，是的话就直接--，如果不是就判断有没有可能变为true，判断能不能变为true就是遍历从i到结尾的每个字词是否存在dict中并且字词之后的部分dp[]为true。
随后就是看dp[0]是false还是true了
class Solution {public: bool wordBreak(string s, unordered_set<string> &dict) { bool dp[s.size()]; memset(dp, 0, sizeof(dp)); for (int i = 0; i < s.size(); i++) { if (dict.count(s.substr(i, s.size() - i))) dp[i] = 1; } for (int i = s.size() - 1; i < s.size(); i--) { if (dp[i] == false) { for (int j = i; j < s.size(); j++) { if (dict.count(s.substr(i, j - i + 1)) && dp[j + 1]) dp[i] = true; if (dp[i]) break; } } } return dp[0]; }};
这题好像个之前做过的leetcode Palindrome Partitioning II有相似的地方。这题比它容易一些。
leetcode[139] Word Break
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。