dp dfs + memo top-down
这个题应该要注意到可能会有大量重复，所以一定可以用memo优化！！所以肯定是一个dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
for (const auto &w : wordDict) {
table.insert(string_view{w});
}
return dfs(string_view{s});
}
bool dfs(string_view sv) {
if (sv.empty()) return true;
if (m.count(sv)) return m[sv];
for (int n = size(sv), i = 1; i <= n; ++i) {
if (table.count(sv.substr(0, i)) && dfs(sv.substr(i))) return m[sv] = true;
}
return m[sv] = false;
}
unordered_set<string_view> table;
unordered_map<string_view, bool> m;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
ws = unordered_set<string>(wordDict.begin(), wordDict.end());
return dfs(s);
}
bool dfs(const string &s) {
if (s.empty()) return true;
if (m.count(s)) return m[s];
string prefix;
int n = s.length();
for (int i = 0; i < n; ++i) {
prefix += s[i];
if (ws.count(prefix) && dfs(s.substr(i + 1))) return true;
}
return m[s] = false;
}
unordered_map<string, bool> m;
unordered_set<string> ws;
};
|
类似palindrom partition bottom-up
划分型dp O(s.length3) m是单词平均长度
f[i]表示前i个字母组成的字符串
最后一步是f[0]到f[n-1]都已经知道了是否能break，遍历一遍看哪种break可以让f[n]为true
所以转移方程是遍历0到n，分别计算每一种划分f[0]到f[n]
f[i] = (f[j] 并且字典里能找到s[j:i] where 0 <= j < i)，即前j个字符和前i个字符之间是s[j:i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = s.length();
vector<bool> f(n + 1, true);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (f[i] = f[j] && (dict.count(s.substr(j, i - j)) > 0)) break;
}
}
return f[n];
}
};
|
用这个
string_view把复杂度降到O(s.length2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string_view> dict(begin(wordDict), end(wordDict));
string_view sv{s};
const int n = size(sv);
vector<int> f(n + 1, true);
for (int i = 1; i <= n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[i] = f[j] && (dict.count(sv.substr(j, i - j)) > 0)) break;
}
}
return f[n];
}
};
|
另外一种方法
O(s.length * wordDict.size * word.length) time
如果wordDict较小且word.length较短，则整体复杂度比常规dp要小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.length();
vector<bool> f(n + 1);
f[0] = true;
for (int i = 0; i < n; ++i) {
for (const auto &w : wordDict) {
if (f[i] && s.substr(i, min(n, w.length())) == w) {
f[i + w.length()] = true;
}
}
}
return f[n];
}
};
|