Work Break I
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".
DP很容易就出来了。possible[i]保存[0,i]是否可以被分割的结果。
possible[i] = true, 当存在possible[k] = true，且[k,i]是dict里的一个word时。否则possible[i] = false。
这种是自底而下的。
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int n = s.length();
if (n == ) return true;
vector<bool> possible(n, false);
for (int i = ; i < n; ++i) {
for (int j = i; j >= ; --j) {
if ((j == || possible[j - ]) && dict.find(s.substr(j, i - j + )) != dict.end()) {
possible[i] = true;
break;
}
}
}
return possible[n - ];
}
};
算法的时间复杂度最坏情况是O(n^2)，空间复杂度是O(n)。
网上也有人用前缀树（Trie树、字典树）实现的。私以为用前缀树还得先将dict里的所有word插进去，时间复杂度为O(n*l+s)，l为word的最大长度，s为dict的大小。如果dict的大小比n大得多，那么整个开销也是不菲的。
只要稍微将上面的代码优化一下，先求出word的最大长度，那么时间复杂度也可以优化到O(n*l+s)。
Work 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"].
直接用回溯就可以了。自顶而下。
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> ret;
bt(s, dict, "", s.length(), ret);
return ret;
}
void bt(string &s, unordered_set<string> &dict, string str, int index, vector<string> &ret) {
if (index < ) {
ret.push_back(str.substr(, str.length() - ));
return;
}
for (int i = index; i >= ; --i) {
string tmp = s.substr(i, index - i + );
if (dict.find(tmp) != dict.end()) {
bt(s, dict, tmp + " " + str, i - , ret);
}
}
}
};