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

2020-03-26

LeetCode

双指针

3 分钟读完 (大约 475 个字) 0次访问

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

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

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

示例1:

输入：s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]
输出：”apple”

示例2:

输入：s = “abpcplea”, d = [“a”,”b”,”c”]
输出：”a”

示例3:

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

方法：双指针（快慢指针）

思路：双指针（快慢指针），一个指针指向字符串s，一个指针指向字典字符串d(i)。

运行数据：执行用时：11 ms，内存消耗：40 MB

// LeetCode指定调用方法
public String findLongestWord(String s, List<String> d) {

    // 最长字串
    String longestWord = "";

    int len = s.length();

    for (String string : d) {
        
        int len1 = longestWord.length(), len2 = string.length();

        if (len > len2) {
            if (len1 < len2
                || (len1 == len2 && string.compareTo(longestWord) < 0)) {
                if (isSubstr(s, len, string, len2)) {
                    longestWord = string;
                }
            }
        } else if (len == len2 && s.compareTo(string) == 0) {
            return string;
        }
    }

    return longestWord;
}

// 双指针（快慢指针）算法，判断是否为子串
public boolean isSubstr(String s, int len, String string, int len2) {

    int i = len - 1, j = len2 - 1;

    while (i >= j && i >= 0 && j >= 0) {

        if (s.charAt(i) == string.charAt(j)) {
            j--;
        }
        i--;
    }

    return j == -1;
}