forked from kamyu104/LintCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
word-break.cpp
43 lines (39 loc) · 1.06 KB
/
word-break.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Time: O(n^2)
// Space: O(n)
class Solution {
public:
/**
* @param s: A string s
* @param dict: A dictionary of words dict
*/
bool wordBreak(string s, unordered_set<string> &dict) {
const int n = s.length();
if (n < 1) {
return true;
}
// Filter out impossible string which alphabet set is not covered
// by dict.
unordered_set<char> chrs;
for (const auto& word : dict) {
for (const auto& c : word) {
chrs.emplace(c);
}
}
for (const auto& c : s) {
if (chrs.find(c) == chrs.end())
return false;
}
// DP
vector<bool> canBreak(n, false);
for (int i = 0; i < n; ++i) {
for (int j = i; j >= 0; --j) {
if ((j == 0 || canBreak[j - 1]) &&
dict.count(s.substr(j, i - j + 1))) {
canBreak[i] = true;
break;
}
}
}
return canBreak[n - 1];
}
};