首页 > 代码库 > 【leetcode】Word Break （middle）
【leetcode】Word Break （middle）
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".
思路：
这道题最开始因为unordered_set纠结了好久。后来突然不知怎么的就顿悟了，也不记得之前到底在纠结什么了...
因为做了Word Break II，这道题就照猫画虎的做了出来。开始我存储了单词到达每个位置时的起始位置，后来发现不用，只要记录能不能到达当前位置即可。
bool wordBreak(string s, unordered_set<string> &dict) { if(dict.empty() || s.empty()) return false; vector<bool> v(s.length() + 1, false); //不需要存储是哪些位置开始的单词到达了v[j] 只要记录到没到就可以了 v[0] = true; for(int i = 1; i <= s.length(); i++) //每一个单词的结束的下一个位置 { for(int j = 0; j < i; j++)//每个单词开始的位置 { if(v[j] && dict.find(s.substr(j, i - j)) != dict.end()) //必须可以到达j 并且可以在字典中找到子串才置为真 { v[i] = true; break; //一旦为真就跳出本层判断 循环下一个结束位置 } } } return v[s.length()]; }
【leetcode】Word Break （middle）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。