文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
- No sort
1 | class Solution { |
Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25bool compare(string& a,string& b)
{
return a.size() != b.size()?a.size() > b.size():a < b;
}
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
sort(d.begin(), d.end(), compare);
for(int i = 0; i < d.size(); i++) {
int m = 0;
int n = 0;
while(m < s.size() && n < d[i].size()) {
if(s[m] == d[i][n]) {
n++;
}
m++;
}
if(n == d[i].size()) {
return d[i];
}
}
return "";
}
};Faster(use find function)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
int index = 0;
int maxLength = 0;
for(int i = 0; i < d.size(); i++) {
int charIndex = -1;
int j = 0;
for(j = 0; j < d[i].size(); j++) {
charIndex = s.find(d[i][j], charIndex + 1);
if(charIndex == -1) {
break;
}
}
if(j == d[i].size() && (maxLength < d[i].size() || (maxLength == d[i].size() && d[i] < d[index]))) {
index = i;
maxLength = d[i].size();
}
}
if(maxLength == 0) {
return "";
}
return d[index];
}
};Faster(use find function + sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25bool compare(string& a,string& b)
{
return a.size() != b.size()?a.size() > b.size():a < b;
}
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
sort(d.begin(), d.end(), compare);
for(int i = 0; i < d.size(); i++) {
int charIndex = -1;
int j = 0;
for(j = 0; j < d[i].size(); j++) {
charIndex = s.find(d[i][j], charIndex + 1);
if(charIndex == -1) {
break;
}
}
if(j == d[i].size()) {
return d[i];
}
}
return "";
}
};
