通过删除字母匹配到字典里最长单词
给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] 输出："apple"
思路：
每一个单词都遍历，找 s 中能不能完全匹配。x 记录 s 的位置，y 记录 dictionary [ i ] 的位置，匹配上 x = y ++，不能匹配 x++，继续往 s 后面搜索。
难点：
判断单词匹配不匹配的上；
找到字典序最小的字符串；
优化：先排序，长字符串排前面，长度相等 字典序小的放前面，再搜索；
string findLongestWord(string s, vector<string>& dictionary) {
int ans = -1, MAX = -1;
for(int i = 0; i < dictionary.size(); i++){
int x = 0, y = 0;
while(x < s.size() && y < dictionary[i].size()){
if(s[x] == dictionary[i][y]) y++;
x++;
}
if(y == dictionary[i].size()){
if(y > MAX){
MAX = y;
ans = i;
}else if(y == MAX){
if(dictionary[i] < dictionary[ans]) ans = i;
}
}
}
if(ans == -1) return "";
return dictionary[ans];
}
优化后：
class Solution {
public:
static bool cmp(string &a,string &b){
if(a.size()==b.size()) return a < b;
return a.size() > b.size();
}
string findLongestWord(string s, vector<string>& dictionary) {
std :: sort(dictionary.begin(),dictionary.end(),cmp);
for(int i = 0; i < dictionary.size(); i++){
int x = 0, y = 0;
while(x < s.size() && y < dictionary[i].size()){
if(s[x] == dictionary[i][y]) y++;
x++;
}
if(y == dictionary[i].size()) return dictionary[i];
}
return "";
}
};