题目描述
给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。 如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
Example 1:
输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”] 输出：”apple”
Example 2:
输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”] 输出：”a”
Constraints:
- 1 <= s.length <= 1000
- 1 <= dictionary.length <= 1000
- 1 <= dictionary[i].length <= 1000
- s 和 dictionary[i] 仅由小写英文字母组成
解题思路
- 暴力匹配，首先排序，长度长的，字典序小的在前面，这样在匹配的时候就可以，一旦匹配成功 就是答案
- 允许删除一些字符串，那就可以随意匹配，当不等于指定的字符时，进行累加判断。
C++代码
class Solution {
public:
static bool cmp(string& a, string& b){
return a.size() > b.size() || (a.size() == b.size() && a < b);
}
bool check(string s, string t){
if(t.size() > s.size()){
return false;
}
int i = 0;
for(auto& ch : t){
while(i < s.size() && s[i] != ch){
i++;
}
if(i >= s.size()){
return false;
}
i++;
}
return true;
}
string findLongestWord(string s, vector<string>& dictionary) {
sort(dictionary.begin(), dictionary.end(), cmp);
for(auto& i : dictionary){
if(check(s, i)){
return i;
}
}
return "";
}
};
