LeetCode 720. 词典中最长的单词

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 字符串 哈希表 排序 字典树

题目描述

✅ 720. 词典中最长的单词

image-20260929104613440

题意分析

从字典中找一个单词，它能够从单字符单词开始，每次只在末尾添加一个字符，并且每一步得到的单词都在字典中。候选越长越好，长度相同时取字典序最小者；没有合法候选就返回空串。

对长度为 L 的候选，构造过程中必然依次经过它长度为 1..L-1 的前缀，因此可以把逐步构造转成前缀是否存在的检查。

解法：哈希集合 + 前缀检查

核心思路

[!blue]

先把全部字典单词加入哈希集合。对于候选 w，依次检查 w 长度为 1 到 len(w)-1 的所有非空真前缀是否在集合中；候选本身来自输入，已经保证存在。

这个条件既必要也充分。若能逐字母构造，每次长度只增加一，途中必须经过每一级前缀，所以它们都要在字典里；反过来，如果每一级前缀都存在，就能从单字符单词开始，每次在末尾补一个字符，逐步得到候选。任意一个前缀缺失，都可以立即放弃当前候选。

单字符单词没有非空真前缀，本身就能作为构造起点，因此检查循环为空时应视为合法。把集合预先建好也意味着查询与输入顺序无关，不必要求短词先出现。

对每个合法候选，先比较长度，再处理字典序：更长就更新答案；长度相同且字典序更小也更新。答案初始化为空串，若始终没有通过全部前缀检查的单词，就保持为空。

解题步骤

  1. 遍历输入，把所有完整单词加入哈希集合。
  2. 对每个候选，从长度 1 开始检查所有非空真前缀，发现缺失就结束该候选的检查。
  3. 若所有前缀都存在，按“长度更大，或同长但字典序更小”的条件更新答案。
  4. 全部候选处理完后返回答案。单字符候选直接合法，无合法候选时返回初始空串。

代码实现

class Solution {
    public String longestWord(String[] words) {
        Set<String> set = new HashSet<>();

        for (String w : words) {
            set.add(w);
        }

        String answer = "";

        for (String w : words) {
            if (!ok720(w, set)) {
                continue;
            }

            // 先取最长，长度相同时取字典序更小的候选。
            if (w.length() > answer.length()
                    || (w.length() == answer.length() && w.compareTo(answer) < 0)) {
                answer = w;
            }
        }

        return answer;
    }

    private boolean ok720(String w, Set<String> set) {
        // 所有非空真前缀都必须在字典中，不能跳过中间长度。
        for (int i = 1; i < w.length(); i++) {
            if (!set.contains(w.substring(0, i))) {
                return false;
            }
        }

        return true;
    }
}

func longestWord(words []string) string {
    set := make(map[string]struct{}, len(words))
    for _, w := range words {
        set[w] = struct{}{}
    }

    answer := ""
    for _, w := range words {
        if !ok720(w, set) {
            continue
        }
        // 先取最长，长度相同时取字典序更小的候选。
        if len(w) > len(answer) || (len(w) == len(answer) && w < answer) {
            answer = w
        }
    }
    return answer
}

func ok720(w string, set map[string]struct{}) bool {
    // 所有非空真前缀都必须在字典中，不能跳过中间长度。
    for i := 1; i < len(w); i++ {
        if _, ok := set[w[:i]]; !ok {
            return false
        }
    }
    return true
}

复杂度分析

设单词数为 W，第 i 个单词长度为 L_i，最长单词长度为 L。

  • 时间复杂度：期望 $O(\sum L_i^2)$。一个单词的各前缀长度之和是平方量级；Java 构造前缀和计算哈希都需要扫描字符，Go 虽可共享前缀内容，哈希仍需按前缀长度计算。
  • 空间复杂度：不计输入字符串本身，集合保存 $O(W)$ 个引用或字符串描述。Java 当前前缀还需要最长 $O(L)$ 的临时空间，总辅助空间为 $O(W+L)$；Go 的前缀切片共享原字符串内容，辅助空间为 $O(W)$。

关键点总结

[!green]

  • 每次只能在末尾添加一个字符，所以合法构造等价于所有中间长度的前缀都存在。
  • 字典集合只表示完整单词存在，不保证它本身可逐步构造，因此仍需检查全部真前缀。
  • 单字符单词是合法起点，不需要空串也出现在字典中。
  • 长度是第一优先级，字典序只用于同长度候选的平局。

易错点总结

[!yellow]

  • 只检查删除最后一个字符后的前缀，会漏掉更短中间前缀的缺失。
  • 一边建立集合一边按输入顺序检查，会让尚未读到的短词被误认为不存在。
  • 要求空串也在字典中，会错误排除所有单字符起点。
  • 同长时直接保留最后遇到的候选，答案会依赖输入顺序，而非字典序。
  • 将每次前缀查询简单当成常数成本，会忽略字符串构造和哈希涉及的字符扫描。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 Trie的终点标记用于确认每一级前缀都是完整单词，本题不仅要求路径存在。
648. 单词替换 中等 同样沿Trie查词终点，原题取最短词根，本题寻找每级前缀都有效的最长单词。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/88897754
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！