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

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

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

示例1：

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

输出: 
"apple"

示例2：

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

说明:

1. 所有输入的字符串只包含小写字母。
2. 字典的大小不会超过 1000。
3. 所有输入的字符串长度不会超过 1000。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题要用到双指针的思想，即一个指针指向目标字符串s，另一个指针指向List<String> d中的每个字符串。我们循环遍历d中的字符串，如果其中字符和s中相等，我们使j指针加一，如果j指针已经到了d中字符串的尾部，判断当前符合要求的字符串是否比结果字符串长，并且是否字典序最小，如果满足条件，则将当前字符串赋值给结果字符串。

具体代码如下：

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String result = "";

        for (String s1 : d) {
            for (int i = 0, j = 0; i < s.length() && j < s1.length(); i++) {
                if (s.charAt(i) == s1.charAt(j)) j++;
                if (j == s1.length()) {
                    if (s1.length() > result.length() || (s1.length() == result.length() && s1.compareTo(result) < 0)) {
                        result = s1;
                    }
                }
            }
        }
        return result;
    }
}