sundeepblue
3/10/2014 - 1:11 AM

## 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 w

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.

``````// DFS solution
bool dfs(string s, unordered_set<string> &dict, int start_idx) {
if(start_idx >= s.size()) return true;
for(int j=start_idx; j<s.size(); j++) {
string t = s.substr(start_idx, j-start_idx+1);
if(dict.find(t) == dict.end()) continue;
if(dfs(s, dict, j+1)) return true;
}
return false;
}
bool wordBreak(string s, unordered_set<string> &dict) {
return dfs(s, dict, 0);
}

// DP solution. Note, the indices are hard to understand in some sense! Be very careful!
bool word_break_DP(string s, unordered_set<string> &dict) {
if(s.empty()) return true;
if(dict.empty()) return false;
vector<bool> F(s.size()+1, false);
F[0] = true;
for(int i=1; i<=s.size()+1; i++) {
for(int j=i-1; j>=0; j--) {
// 为何是f[j] 而不是f[j-1]? 因为f的长度是s.size()+1, f[j]指的是从0到j-1的字符串的bool值
if(F[j] && dict.find(s.substr(j, i-j)) != dict.end())
F[i] = true;
break;
}
}
return F[s.size()];
}``````