题目描述
思路解析动画文字版
记住这句:「排序让前缀先到，集合判前缀可达」。下面每一帧都在套它。本题演示数据答案是 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题