-
Notifications
You must be signed in to change notification settings - Fork 0
/
139-Word Break.cpp
37 lines (37 loc) · 1.19 KB
/
139-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
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
vector<int> dp(n+1, 0);
// dp[i] = 1 indicates that substring s[0]-s[i-1] can be broken
// into dictionary words.
dp[0] = 1;
for(int i = 1; i <= n; ++i){
for(auto w : wordDict){
int len = w.size();
if(i - len >= 0 && dp[i-len] && s.substr(i-len, len) == w){
dp[i] = 1;
break;
}
}
}
return dp[n];
}
// bool wordBreak(string s, vector<string>& wordDict) {
// int n = s.size();
// vector<int> dp(n+1, 0);
// // dp[i] = 1 indicates that substring s[0]-s[i] can be broken
// // into dictionary words.
// unordered_set<string> dict(wordDict.begin(), wordDict.end());
// dp[0] = 1;
// for(int i = 1; i <= n; ++i){
// for(int j = 0; j < i; ++j){
// if(dp[j] && dict.find(s.substr(j, i-j)) != dict.end()){
// dp[i] = 1;
// break;
// }
// }
// }
// return dp[n];
// }
};