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

题目描述

这是 LeetCode 上的 524. 通过删除字母匹配到字典里最长单词 ，难度为 中等。

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。

如果答案不存在，则返回空字符串。

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]

输出："apple"

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]

输出："a"

提示：

• $1 <= s.length <= 1000$
• $1 <= dictionary.length <= 1000$
• $1 <= dictionary[i].length <= 1000$
• s 和 dictionary[i] 仅由小写英文字母组成

---

排序 + 双指针 + 贪心

根据题意，我们需要找到 dictionary 中为 s 的子序列，且「长度最长（优先级 $1$）」及「字典序最小（优先级 $2$）」的字符串。

数据范围全是 $1000$。

我们可以先对 dictionary 根据题意进行自定义排序：

1. 长度不同的字符串，按照字符串长度排倒序；
2. 长度相同的，则按照字典序排升序。

然后我们只需要对 dictionary 进行顺序查找，找到的第一个符合条件的字符串即是答案。

具体的，我们可以使用「贪心」思想的「双指针」实现来进行检查：

1. 使用两个指针 i 和 j 分别代表检查到 s 和 dictionary[x] 中的哪位字符；
2. 当 s[i] != dictionary[x][j]，我们使 i 指针右移，直到找到 s 中第一位与 dictionary[x][j] 对得上的位置，然后当 i 和 j 同时右移，匹配下一个字符；
3. 重复步骤 $2$，直到整个 dictionary[x] 被匹配完。

证明：对于某个字符 dictionary[x][j] 而言，选择 s 中 当前 所能选择的下标最小的位置进行匹配，对于后续所能进行选择方案，会严格覆盖不是选择下标最小的位置，因此结果不会变差。

Java 代码：

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, (a,b)->{
            if (a.length() != b.length()) return b.length() - a.length();
            return a.compareTo(b);
        });
        int n = s.length();
        for (String ss : dictionary) {
            int m = ss.length();
            int i = 0, j = 0;
            while (i < n && j < m) {
                if (s.charAt(i) == ss.charAt(j)) j++;
                i++;
            }
            if (j == m) return ss;
        }
        return "";
    }
}

C++ 代码：

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b) {
            if (a.length() != b.length()) return b.length() < a.length();
            return a < b;
        });
        int n = s.length();
        for (const string& word : dictionary) {
            int m = word.length();
            int i = 0, j = 0;
            while (i < n && j < m) {
                if (s[i] == word[j]) j++;
                i++;
            }
            if (j == m) return word;
        }
        return "";
    }
};

Python 代码：

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        dictionary.sort(key=lambda x: (-len(x), x))
        n = len(s)
        for word in dictionary:
            m = len(word)
            i, j = 0, 0
            while i < n and j < m:
                if s[i] == word[j]: j += 1
                i += 1
            if j == m: return word
        return ""

TypeScript 代码：

function findLongestWord(s: string, dictionary: string[]): string {
    dictionary.sort((a, b) => {
        if (a.length !== b.length) return b.length - a.length;
        return a.localeCompare(b);
    });
    const n = s.length;
    for (const word of dictionary) {
        const m = word.length;
        let i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] === word[j]) j++;
            i++;
        }
        if (j === m) return word;
    }
    return "";  
};

• 时间复杂度：令 n 为 s 的长度，m 为 dictionary 的长度。排序复杂度为 $O(m\log{m})$；对 dictionary 中的每个字符串进行检查，单个字符串的检查复杂度为 $O(\min(n, dictionary[i]))\approx O(n)$。整体复杂度为 $O(m\log{m} + m \times n)$
• 空间复杂度：$O(\log{m})$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.524 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。