首页 > 代码库 > Word Break && Word Break II
Word Break && Word Break II
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".
说明： 深度搜索，一定要记忆下每次走完的结果（此处记下筛掉的情况）。
bool judge(string s, unordered_set<string> &dict, vector<bool> &tag) { if(s == "") return true; for(int i = 1; i <= s.length(); ++i) { if(tag[s.size()-i] && dict.find(s.substr(0, i)) != dict.end()) { if (judge(s.substr(i, s.size()-i), dict, tag)) return true; else tag[s.size()-i] = 0; } } return false;}class Solution {public: bool wordBreak(string s, unordered_set<string> &dict) { if(s == "") return true; vector<bool> tag(s.size()+1, true); //the value is the result that (index) length of reserved string can return; return judge(s, dict, tag); }};
Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
说明： 方法比较巧妙。记忆下每个位置开始的所有能成回文串的结束位置。然后深搜。
void dfs(string s, vector<vector<int> > & Reach, int Id, string path, vector<string> &vec) { if(Id == s.size()) { vec.push_back(path); return; } for(size_t i = 0; i < Reach[Id].size(); ++i) { path = path + (Id == 0 ? s.substr(Id, Reach[Id][i]) : " " + s.substr(Id, Reach[Id][i]-Id)); dfs(s, Reach, Reach[Id][i], path, vec); path.erase(path.end()-(Id == 0 ? Reach[Id][i] : (Reach[Id][i]-Id+1)), path.end()); }}class Solution {public: vector<string> wordBreak(string s, unordered_set<string> &dict) { vector<string> vec; int n = s.size(); if(n == 0) return vec; vector<vector<int> > reachable(n, vector<int>()); for(int end = n; end > 0; --end) { if(end < n && reachable[end].empty()) continue; for(int start = 0; start < end; ++start) { if(dict.find(s.substr(start, end-start)) != dict.end()) reachable[start].push_back(end); } } dfs(s, reachable, 0, string(""), vec); return vec; }};
两题公有的易超时反例：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaa……aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab