题目描述
思路解析
一句话答案：LeetCode 720 词典中最长的单词：找每个前缀都在词典里的最长词，把所有词插进 Trie 字典树、逐词检查沿路每一步是不是词尾，等长取字典序最小，时间与空间都是 O(L)。
词典里找能逐字母长出来的最长词，返回什么
给一个字符串数组 words。要找一个最长的词 w：它去掉末尾若干字母后，每一个前缀都还在 words 里。多个最长的取字典序最小，一个都没有就返回空串。题面例子 words=["w","wo","wor","worl","world"] 返回 "world"；words=["a","banana","app","appl","ap","apply","apple"] 返回 "apple"。
词在不在词典，和能不能拼出来是两码事
把词典塞进哈希集合、看目标词在不在里面，答的却是错的问题。"world" 在词典里，不代表它能逐字母拼出来：只要 "wor" 缺席，就没法从 "wo" 走到 "worl"，"world" 照样拼不出。真正要查的是它每一个前缀 w、wo、wor、worl 都在词典里，缺一步整条链就断了。
一个词合法，就是沿路每个前缀都是词典里的词
把要求说死：w 合法，当且仅当从空串起，一个字母一个字母往后添，每添一步得到的前缀都恰好是词典里的某个词，一步都不能落空。
能存下所有词、又能顺着字母快速查前缀——这个逐前缀往下探的结构就是 Trie 字典树，也就是把有公共前缀的词合并成一棵树、沿树往下每一步添一个字母。把所有词插进去，每个词末字母的节点打上"是词尾"的标记。查 w 时顺它的字母从根往下走，每落到一个节点就看有没有词尾标记，只要有一步没有，这层前缀就不是词典里的词，w 当场判死。
逐词走一遍 Trie，长度和字典序一起挑答案
建完树，拿每个词走一遍：全程每个落脚节点都带词尾标记，才算能构建。通过的词和当前答案 ans 比长短，比 ans 长（len(ans) ＜ len(w)）就换成它；一样长则留字典序小的，即 ans ＞ w 时换成 w。不依赖排序，扫完所有词，ans 就是最长、同长里字典序最小的那个。
拿题面的 apple 那组词沿字典树逐词往下探
先把七个词都插进 Trie，再逐个查。"a" 走一步落到带词尾标记的节点，通过，ans="a"。"banana" 第一步的 "b" 节点没有词尾标记，判死。"app" 走 a、ap、app 三步全带标记，比 "a" 长，ans="app"；"appl" 再多一步也带标记，ans="appl"；"ap" 能过但只有 2 长，不换；"apply" 五步全带标记，长 5，ans="apply"。
最后是 "apple"，五步也全带标记，长度同样是 5。比字典序：前四位 appl 相同，第五位 e ＜ y，"apple" ＜ "apply"，ans ＞ w 成立，答案换成 "apple"。返回 "apple"，长度 5。
为什么是 O(L)，三个边界先想清
设 L 是所有词的总字符数。建 Trie 时每个字母插一次，逐词查询又把每个字母走一遍，两趟都是 O(L)；节点数最多和总字符数同阶，空间也是 O(L)。等长比字典序、词尾标记别漏是两处易踩的坑。全是单字母词时都能构建，答案取里面字典序最小的。没有单字母词打底，谁都拼不出第一步，ans 始终是空串。单字母词去掉末位是空串，空前缀天然合法，永远通过。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句:「排序让前缀先到，集合判前缀可达」。下面每一帧都在套它。本题演示数据答案是 car。
先看原始词典：cat、c、car、dog、ca，顺序是乱的。这样扫的时候，可能先碰到 car 却还没确认 ca、c，没法判断它能不能构建。所以第一件事是排序。
按「长度从短到长、同长度按字典序」排好后变成 c、ca、car、cat、dog。短的排前面，保证了一个关键性质：任何一个词的前缀，长度都更短，一定已经排在它前面、先被处理过。
准备一个集合 S，专门装「已经确认能逐字构建出来」的词，现在它是空的。答案 ans 也先设成空串。接下来从最短的词开始，一个一个判断、一个一个往 S 里收。
轮到第 0 个词 "c"，它只有一个字母。长度为 1 的词去掉末位就是空串。
空前缀天然算在集合里，所以单字母词永远能构建，"c" 直接通过，准备收进集合。
把 "c" 收进集合 S（绿色），它比当前答案更长，于是答案更新成 "c"。
轮到第 1 个词 "ca"。把末尾的 "a" 去掉，得到前缀 "c"。只要 "c" 已经在集合 S 里，就说明 "ca" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
去集合里找前缀 "c"，找到了！高亮的就是它。这说明 "ca" 的每一步前缀都在词典里、都能拼出来，所以 "ca" 也能构建。
把 "ca" 收进集合 S（绿色），它比当前答案更长，于是答案更新成 "ca"。
轮到第 2 个词 "car"。把末尾的 "r" 去掉，得到前缀 "ca"。只要 "ca" 已经在集合 S 里，就说明 "car" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
去集合里找前缀 "ca"，找到了！高亮的就是它。这说明 "car" 的每一步前缀都在词典里、都能拼出来，所以 "car" 也能构建。
把 "car" 收进集合 S（绿色），它比当前答案更长，于是答案更新成 "car"。
轮到第 3 个词 "cat"。把末尾的 "t" 去掉，得到前缀 "ca"。只要 "ca" 已经在集合 S 里，就说明 "cat" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
去集合里找前缀 "ca"，找到了！高亮的就是它。这说明 "cat" 的每一步前缀都在词典里、都能拼出来，所以 "cat" 也能构建。
把 "cat" 收进集合 S。它和当前答案 "car" 一样长，但字典序不比 "car" 更小，所以答案保持 "car" 不变。这正是「同长取字典序最小」的体现。
轮到第 4 个词 "dog"。把末尾的 "g" 去掉，得到前缀 "do"。只要 "do" 已经在集合 S 里，就说明 "dog" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
去集合里找前缀 "do"，没有这一行。也就是说 "do" 自己都拼不出来，那建立在它之上的 "dog" 自然也拼不出来。"dog" 标红，判定不可构建。
"dog" 不可构建，直接跳过，不放进集合，答案也不动。它变灰，表示彻底出局。继续看下一个词。
扫完一遍。能构建的词是 c、ca、car、cat 四个，dog 因为缺前缀出局。最长的是长度 3 的 car 和 cat 两个，到了「同长取字典序最小」的关键一步。
car 和 cat 都长 3，比字典序：前两位都是 ca，第三位 r 比 t 小，所以 car 更小。因为我们排序时 car 排在 cat 前面、先被收下当答案，后来的 cat 同长又不更小就没顶替它。最终答案是 car。
边界先想清：全单字母、无可构建词、只有一个单字母词。
面试重点：Trie 与「排序+集合」是等价两条路，理解前缀递推关系。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Trie: def __init__(self): self.children: List[Optional[Trie]] = [None] * 26 self.is_end = False def insert(self, w: str): node = self for c in w: idx = ord(c) - ord("a") if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.is_end = True def search(self, w: str) -> bool: node = self for c in w: idx = ord(c) - ord("a") if node.children[idx] is None: return False node = node.children[idx] if not node.is_end: return False return Trueclass Solution: def longestWord(self, words: List[str]) -> str: trie = Trie() for w in words: trie.insert(w) ans = "" for w in words: if trie.search(w) and ( len(ans) < len(w) or (len(ans) == len(w) and ans > w) ): ans = w return ans复杂度
- 时间：O(L)，L 为所有词总字符数：Trie 建树与逐词查询各扫一遍字符
- 空间：O(L)，Trie 节点数最多与总字符数同阶
易错点
面试追问把动画讲成自己的话
追问不排序能不能做？
追问集合为什么够用、不会漏判？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单调递增的数字
LeetCode 738 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题