首页 > 代码库 > [LeetCode] Word Break
[LeetCode] Word Break
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".
Solution:
LTE Code:
string srcStr;unordered_set<string> dic;bool word_break(int start){ //cout << "Start with " << start << endl; if(start >= srcStr.length()) return true; for(int i = start;i < srcStr.length();i++) { string curStr = srcStr.substr(start, i - start + 1); if(dic.find(curStr) != dic.end()) { //return word_break(i+1); //The reason is that if current recursion return false, doest not mean the //break should fail, we need to check other combinations. if(word_break(i + 1)) return true; else continue; } else continue; } return false;}bool wordBreak(string s, unordered_set<string> &dict) { srcStr = s; dic = dict; return word_break(0); }
AC Code:
string srcStr;unordered_set<string> dic;int visited[1000][1000];int checked[1000];string srcStr;unordered_set<string> dic;int visited[1000][1000];int checked[1000];bool word_break(int start){ //cout << "Start with " << start << endl; if(start >= srcStr.length()) return true; for(int i = start;i < srcStr.length();i++) { string curStr = srcStr.substr(start, i - start + 1); int finded = 0; if(visited[start][i] == 1) finded = true; else if(visited[start][i] == 2) finded = false; else { finded = (dic.find(curStr) != dic.end()) ? 1 : 2; visited[start][i] = finded; } if(finded == 1) { if(checked[i + 1] == 1) return true; else if(checked[i + 1] == 2) continue; else { checked[i + 1] = word_break(i + 1) ? 1 : 2; if(checked[i + 1] == 1) return true; else continue; } } else continue; } return false;}bool wordBreak(string s, unordered_set<string> &dict) { srcStr = s; dic = dict; for(int i = 0;i < 1000;i++) memset(visited[i], 0, sizeof(int) * 1000); memset(checked, 0, sizeof(int) * 1000); if(s.length() > 1000) return false; return word_break(0); }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。