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

2024-03-01 HGNULB 约 8 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

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

题意分析

给一个字符串 s 和一个字符串数组 dictionary，要在字典里找出这样一个词：只通过删除 s 中的某些字符（不能重排、不能替换）就能得到它。在所有满足条件的词里返回最长的那个，长度相同时返回字典序最小的那个，一个都没有就返回空字符串。

「只删不换、不改顺序」这句话是全题的题眼，它等价于说这个词必须是 s 的子序列——字符相对次序必须保持一致，但可以不连续。

判定标准是两层的：先比长度，长度打平再比字典序，而且是取字典序更小的。两层规则必须写成一个复合条件，漏掉任何一层都会在特定用例上出错。

约束上 s 与字典中每个词的长度都在千级，字典规模也在千级，说明「对每个词单独扫一遍 s」这种量级是可以接受的。边界包括：字典里可能没有任何词能匹配，此时返回空串；也可能某个词就等于 s 本身，这仍然算合法（删除零个字符）。

解法：枚举词典并双指针匹配

核心思路

最直接的想法是枚举 s 的所有子序列再去字典里查，但子序列个数是 $2^{ s }$，在 s 长度上千时完全不可行。方向必须反过来：不是从 s 生成候选，而是拿字典里的每个词去 s 里验证。

于是问题归约成一个更小的问题：给定 word 和 s，判断 word 是不是 s 的子序列。这里的关键观察是贪心可行——匹配 word 的第 $i$ 个字符时，在 s 中选择尽可能靠左的那个位置总是不劣的，因为把匹配位置往左挪只会给后面的字符留下更多的可选空间，绝不会让原本能匹配的变得不能匹配。

贪心成立后，判定就退化成一次同向扫描：一个指针 $i$ 指向 word 的待匹配位置，另一个指针 $j$ 扫过 s，字符相等就把 $i$ 推进一格，无论是否相等 $j$ 都推进一格。整个过程维持的不变量是：word 的前 $i$ 个字符已经匹配到 s 的前 $j$ 个字符里，且用掉的下标是所有可行方案中最靠左的一组。扫完 s 后 $i$ 是否走到末尾就是答案。

最外层再套一个「边扫边取最优」的比较：维护当前最优答案 answer，每当一个词通过判定，就按「更长」或「等长且字典序更小」这个复合条件替换它。这样只需一趟遍历，不必先收集再排序。

解题步骤

把答案初始化为空字符串。空串既是「无解」的正确返回值，也天然是比较的下界——任何合法词的长度都不小于 0，所以不需要额外的哨兵判断。

遍历字典中的每个词，先做子序列判定，不通过就直接跳过。把判定放在比较之前，可以避免对不合法的词做无谓的字符串比较。

判定函数里用两个指针同向扫描：$i$ 指向词、$j$ 指向 s。相等时两个都前进，不等时只前进 $j$。只推进 $j$ 的含义是「s 的这个字符被删掉」，这正对应题目允许的操作。

循环条件是两个指针都未越界，退出后用 $i$ 是否等于词长来判定成功。用 $i$ 而不是 $j$ 判定，是因为 s 有剩余字符完全没关系，词没匹配完才是失败。

更新答案时用一个复合条件：长度更大，或者长度相等且字典序更小。两个分支必须写在同一个 if 里，如果拆成先比长度再比字典序的两段独立逻辑，很容易出现「短词把长词覆盖掉」的问题。

遍历结束返回答案。因为每次替换都保证了新值严格优于旧值，所以最终留下的一定是全局最优。

以 s = "abpcplea"、dictionary = ["ale", "apple", "monkey", "plea"] 走一遍：answer 初始为 ""。

第一个词 "ale"。指针从 $i=0, j=0$ 出发：s[0]='a' 与 'a' 相等，$i=1, j=1$；s[1]='b' 不等于 'l'，$j=2$；'p'、'c'、'p' 都不是 'l'，$j$ 推到 5；s[5]='l' 相等，$i=2, j=6$；s[6]='e' 相等，$i=3, j=7$。$i$ 等于词长 3，判定通过。answer 从 "" 变成 "ale"，因为长度 3 大于 0。

第二个词 "apple"。匹配过程：'a' 对上 s[0]；'p' 对上 s[2]；第二个 'p' 对上 s[4]；'l' 对上 s[5]；'e' 对上 s[6]。$i$ 走到 5 等于词长，通过。长度 5 大于当前答案的 3，answer 更新为 "apple"。

第三个词 "monkey"。$j$ 从头扫到尾都没找到 'm'，退出时 $i$ 仍为 0，不等于词长 6，判定失败，跳过。

第四个词 "plea"。'p' 对上 s[2]，'l' 对上 s[5]，'e' 对上 s[6]，'a' 对上 s[7]，通过。但它长度为 4，既不大于 5，也不等于 5，复合条件两个分支都不成立，answer 保持 "apple"。

遍历结束，返回 "apple"。若把字典换成 ["a", "b", "c"]，三个词长度都是 1："a" 先把答案从 "" 升到 "a"；"b" 等长但字典序更大，不替换；"c" 同理，最终返回 "a"，正是字典序最小的那个。

代码实现

class Solution {
    // 最长优先、同长同序最小优先是两层判断规则，答案更新可以边扫边比较。
    public String findLongestWord(String s, String[] dictionary) {
        String answer = "";
        for (String word : dictionary) {
            if (!isSubsequence(word, s)) {
                continue;
            }
            if (word.length() > answer.length() || (word.length() == answer.length() && word.compareTo(answer) < 0)) {
                answer = word;
            }
        }
        return answer;
    }

    private boolean isSubsequence(String a, String b) {
        int i = 0;
        int j = 0;
        while (i < a.length() && j < b.length()) {
            if (a.charAt(i) == b.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == a.length();
    }
}

func findLongestWord(s string, dictionary []string) string {
    // 最长优先、同长同序最小优先是两层判断规则，答案更新可以边扫边比较。
    answer := ""
    for _, w := range dictionary {
        if !isSubseq564(w, s) {
            continue
        }
        if len(w) > len(answer) || (len(w) == len(answer) && w < answer) {
            answer = w
        }
    }
    return answer
}

func isSubseq564(a, b string) bool {
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] == b[j] {
            i++
        }
        j++
    }
    return i == len(a)
}

复杂度分析

时间复杂度：$O(N \cdot s + \text{sumLen})$，其中 $N$ 是字典词数、$\text{sumLen}$ 是所有词的长度之和。每个词的判定最多把 $j$ 从头推到尾，代价是 $ s $；字典序比较的总代价不超过所有词长之和。

空间复杂度：$O(1)$，只用了两个下标和一个指向已有字符串的答案引用，没有开辟与输入规模相关的结构。

关键点总结

「只删不重排」是子序列的同义表述。看到这句话就应该立刻把问题翻译成子序列判定，而不是去想删除操作本身。

候选空间爆炸时反转验证方向：不从长串生成子序列，而是拿每个候选去长串里验证，把指数级降到线性级。

子序列判定的贪心正确性来自「匹配位置越靠左，后续选择越多」这条交换论证。面试中被追问为什么不用回溯时，这就是标准答案。

多层排序规则要合成一个复合布尔条件，不要拆成多趟比较，否则边界上极易互相覆盖。

面试视角：先给出这个 $O(N \cdot s )$ 的解法作为基线，再主动提出优化方向——若字典规模远大于 s，可以对 s 预处理出「每个位置之后每个字母的下一次出现下标」，把单次判定降到词长级别。能说出这个升级路径，比只写出基线解法评价高得多。

易错点总结

错误写法：更新答案时只比长度，忘记等长取字典序小的分支。s = "abce"、dictionary = ["abe", "abc"] → 两个词都合法且等长，先遇到的 "abe" 被保留，正确答案是 "abc"。

错误写法：等长时的比较方向写反，取字典序更大的。s = "abpcplea"、dictionary = ["apple", "aplee"]（假设都合法）→ 会返回字典序更大的那个，与题目要求相反。

错误写法：把两层规则拆成先按长度更新、再单独一轮按字典序更新。任何同时含长词和短小字典序词的用例 → 第二轮会用一个更短但字典序更小的词覆盖掉正确答案。

错误写法：子序列判定结束后用 j == s.length() 判定成功。s = "abpcplea"、词为 "ale" → 匹配完成时 $j$ 停在 7 没走到末尾，合法的词被误判为失败。

错误写法：判定循环里字符不等时把两个指针都前进。s = "abpcplea"、词为 "ale" → 'l' 与 s[1]='b' 不等时词指针也跳过了 'l'，实际比较的成了子串而非子序列，返回空串。

错误写法：把答案初始化为字典的第一个词而不是空串。s = "x"、dictionary = ["abc"] → 没有任何词合法时返回了 "abc"，正确答案是 ""。

错误写法：为了「优化」先按长度降序排字典再返回第一个匹配项，但排序时没有把等长情况按字典序升序处理。dictionary = ["abe", "abc"] → 排序不稳定或规则不全时返回 "abe"。

错误写法：认为词等于 s 本身不算合法而额外加了长度小于 |s| 的过滤。s = "abc"、dictionary = ["abc"] → 返回空串，正确答案是 "abc"，因为删除零个字符也是允许的。

相似题目

题目	难度	考察点
392. 判断子序列	简单	单次子序列判定，是本题内层函数的裸题形式
792. 匹配子序列的单词数	中等	词数极大时必须换成分桶或下一位置表来加速判定
1143. 最长公共子序列	中等	两串都可删时贪心失效，必须退回二维动态规划