[LeetCode] 524. Longest Word in Dictionary through Deleting

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:
Input:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]

Output:
“apple”

Example 2:
Input:
s = “abpcplea”, d = [“a”,”b”,”c”]

Output:
“a”

Note:
All the strings in the input will only contain lower-case letters.
The size of the dictionary won’t exceed 1,000.
The length of all the strings in the input won’t exceed 1,000.

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

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是双指针，类似于392题找子序列。因为 s 删除字母是无序的，所以只能通过判断子序列的方式来看 dictionary 中的每个单词是不是由 s 删减而来。如果你找到一个单词了，之后再有一个单词，他也是 s 的子序列的话，需要用 str.compareTo() 额外判断 str 的字典序是否比 res 小，若是则替换 res，从而得到字典序最小的结果。

a.compareTo(b) 这个函数如果返回负数，说明 a 的字典序比 b 小，返回正数说明 a 的字典序比 b 大。

复杂度

时间O(mn) - 要与m个单词比较，单词平均长度为n
空间O(1)

代码

Java实现

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = "";
        for (String word : dictionary) {
            if (helper(word, s)) {
                if (word.length() > res.length()) {
                    res = word;
                } else if (word.length() == res.length() && word.compareTo(res) < 0) {
                    res = word;
                }
            }
        }
        return res;
    }

    private boolean helper(String s, String t) {
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
}

相关题目

392. Is Subsequence
524. Longest Word in Dictionary through Deleting
720. Longest Word in Dictionary