Leetcode 139. Word Break

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Word Break

2. Solution

  • Version 1
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
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(s.size() == 0) {
return false;
}
vector<int> flags(s.size(), -1);
unordered_set<string> dict(wordDict.begin(), wordDict.end());
return split(s, dict, flags, 0);
}
bool split(string& s, set<string>& dict, vector<int>& flags, int start) {
if(start == s.size()) {
return true;
}
if(flags[start] != -1) {
return flags[start];
}
for(int i = start + 1; i <= s.size(); i++) {
string temp = s.substr(start, i - start);
if(dict.find(temp) != dict.end() && split(s, dict, flags, i)) {
flags[start] = 1;
return true;
}
}
flags[start] = 0;
return false;
}
};
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(s.size() == 0) {
return false;
}
set<string> dict(wordDict.begin(), wordDict.end());
vector<bool> flag(s.size() + 1, false);
flag[0] = true;
for(int i = 1; i <= s.size(); i++) {
for(int j = 0; j < i; j++) {
if(flag[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
flag[i] = true;
break;
}
}
}
return flag[s.size()];
}
};
  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(s.size() == 0) {
return false;
}
set<string> dict(wordDict.begin(), wordDict.end());
vector<bool> flag(s.size() + 1, false);
flag[0] = true;
for(int i = 1; i <= s.size(); i++) {
for(int j = i - 1; j >= 0; j--) {
if(flag[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
flag[i] = true;
break;
}
}
}
return flag[s.size()];
}
};

Reference

  1. https://leetcode.com/problems/word-break/
如果有收获,可以请我喝杯咖啡!