LeetCode 每日一题 524. 通过删除字母匹配到字典里最长单词

524. 通过删除字母匹配到字典里最长单词

最长子序列

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"

题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。

通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。

代码：

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
    string res = "";
    for(auto ss: dictionary)
    {
        for(int i = 0, j = 0; i < ss.size(); i++)
        {
            while(j < s.size() && s[j] != ss[i]) j++;
            if (i == ss.size() -1 && s[j] == ss[i])
                if ( ss.size() > res.size() )
                    res = ss;
                else if ( ss.size() == res.size() && ss < res)
                    res = ss;
            if (j < s.size() && s[j] == ss[i]) j++;
        }
    }
    return res;        
    }
};