题目描述 通过删除字母匹配到字典里最长单词

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"

解题思路

暴力搜一遍，设置一个res表示当前最长的字符串。把符合条件的字符串和塔比较留下符合条件的那个。
稍微加快一点，如果要匹配的字符串的长度小于当前res的长度，跳过。

代码

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        string res="";
        if(d.size()==0||s.empty()) return res;
        for(int i=d.size()-1;i>=0;i--){
            if(res.size()>d[i].size()) continue;
            int j=0, k=0;

            while(j<s.size()&&k<d[i].size()){
                while(j<s.size() && s[j]!=d[i][k]){
                    j++;
                }
                if(s[j]==d[i][k]){
                    k++; j++;
                }
            }
            if(k==d[i].size()){
                if(k>res.size()) res = d[i];
                else if(k==res.size()) res = res < d[i] ? res : d[i];
            }
        }
        return res;
    }
};