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

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为
标签
数组 字符串 排序 双指针

题目描述

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

image-20260928224259989

题意分析

删除字符会保留剩余字符的相对顺序，因此要从字典中找出属于 s 的子序列的单词。答案先按长度取最大值，长度相同时再取字典序最小值；没有任何匹配时返回空串。

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

核心思路

[!blue]

对每个候选单词单独判断子序列关系。用 i 指向候选中下一个待匹配字符，用 j 从左到右扫描源串：字符相等就推进 i，无论是否相等都推进 j。因此已经匹配的字符顺序不变，源串中未匹配的字符对应删除操作。

总是使用最早可用的相同字符不会漏解。假设某个合法匹配使用了更靠后的位置，把这一次匹配换到较早位置后，后续原有的匹配位置仍然有效。逐个字符这样处理，就为剩余字符保留了最多空间。

当 i 到达候选末尾，说明全部字符已经按顺序匹配，候选有效；若源串扫描完仍有候选字符未匹配，则无效。对所有有效候选维护 answer：更长时替换，等长且字典序更小时替换。这样每轮后 answer 都是已经检查过的单词中的最优解。

解题步骤

  1. 将答案初始化为空串，逐个检查字典单词。
  2. 每个单词都重新将两个游标归零，按字符是否相等推进候选游标，源串游标每轮都前进。
  3. 用候选是否全部匹配判断成功；成功时源串可以还有剩余字符。
  4. 仅对成功的候选比较长度和字典序，更新答案。
  5. 遍历完字典后返回答案；始终没有匹配时保留初始空串。

代码实现

class Solution {
    // 最长优先、同长字典序最小优先是两层判断规则，答案更新可以边扫边比较。
    public String findLongestWord(String s, List<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(D\lvert s\rvert)$，其中 $D$ 为字典词数。每个候选最多扫描源串一次；有效候选长度不超过 $\lvert s\rvert$，等长时的字典序比较也不超过这个量级。
  • 空间复杂度：$O(1)$，答案引用已有单词，匹配只用两个游标。

关键点总结

[!green]

  • 不能匹配的源字符可以删除，但不能跳过候选所需字符。
  • 长度优先，字典序只用于同长比较。

易错点总结

[!yellow]

  • 只比较长度，会让等长结果取决于字典输入顺序。
  • 用源串是否扫描完判断成功，会拒绝提前完成的合法候选。
  • 直接把字典首词设为答案，可能在无解时返回不合法单词。

相似题目

题目 难度 关联与区别
392. 判断子序列 简单 检查每个候选词是否为源串子序列是基础，本题再按长度和字典序选择最优候选。
792. 匹配子序列的单词数 中等 同样让多个词匹配一个长串，原题统计匹配数量，本题返回最长且字典序最小者。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/leetcode-524
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！