| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (44.88%) | 57 | - |
Tags
two-pointers | sort
Companies
google
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
1
2
3
4
5
| 输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"
|
示例 2:
1
2
3
4
5
| 输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"
|
说明:
- 所有输入的字符串只包含小写字母。
- 字典的大小不会超过 1000。
- 所有输入的字符串长度不会超过 1000。
Discussion | Solution
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
44
45
46
47
48
49
50
51
52
| class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
std::vector<std::string> res;
for(const auto &el: d) {
int k = 0; //
size_t cnt = 0; //count for equal chars
for(size_t i=0; i<el.size(); i++) {
for(size_t j=k; j<s.size(); j++) {
if(s[j] == el[i]) {
cnt++;
k = j+1;
break;
}
}
}
if (cnt == el.size())
{
res.push_back(el);
}
}
if(res.empty()) {
return std::string();
}
if(res.size() == 1) {
return res[0];
}
std::sort(res.begin(), res.end(), [](const std::string &a, const std::string &b){
return a.size() > b.size();
});
std::vector<std::string> res2;
for(size_t i = 0; i < res.size() -1; i++) {
if(res[i].size() != res[i+1].size()) {
res2.push_back(res[i]);
break;
} else {
res2.push_back(res[i]);
res2.push_back(res[i+1]);
}
}
std::sort(res2.begin(), res2.end());
return res2[0];
}
};
|