如何用 Trie 找所有前缀都存在的最长单词？

简化版

把所有单词插入 Trie，然后只沿着 isEnd=true 的节点继续 DFS。因为要求单词的每一级前缀都存在，路径上每个字符节点都必须是一个完整单词结尾；在 DFS 中更新最长答案即可。

详细版

题目常见问法是：给一个单词列表，找最长的单词，要求它可以由列表中其他单词逐字符构建出来。例如 world 需要 w、wo、wor、worl 都存在。

做法：

把所有单词插入 Trie，每个单词末尾标记 isEnd=true，并可保存完整单词。
从根节点 DFS。
只有当前孩子节点 isEnd=true 时，才允许继续进入这个孩子。
每到一个合法单词节点，就用长度和字典序更新答案。
若长度相同，通常返回字典序更小的单词。

void dfs(Trie node) {
    if (node.word != null) updateAnswer(node.word);
    for (int i = 0; i < 26; i++) {
        Trie child = node.children[i];
        if (child != null && child.word != null) dfs(child);
    }
}

如果单词总字符数为 S，建树 O(S)，DFS 最多访问合法前缀节点，整体 O(S)。

完整版教学

一、题目真正限制是什么

这题不是单纯找最长单词，而是找“每个前缀都在词典中”的最长单词。比如 apple 存在，但如果词典缺少 appl，它就不合法。这个限制让普通按长度排序检查变得容易漏细节。

words = [a, ap, app, appl, apple, apply, banana]

apple 合法：a, ap, app, appl 都存在
apply 合法：a, ap, app, appl 都存在
banana 不合法：b 不存在

Trie 天然把前缀展开成路径。只要保证路径上的每个节点都是完整单词，就能判断某个单词是否可以逐级构建。

二、为什么 DFS 只能走 isEnd 节点

Trie 中一个节点存在，只代表某个前缀存在于某些单词路径中，不代表这个前缀本身是一个完整单词。例如插入 apple 后，a、ap、app 节点都会存在，但如果它们没有 isEnd=true，就不能说明这些前缀在词典里。

只插入 apple:
root -> a -> p -> p -> l -> e(isEnd)

节点 a 存在，但 a 不是单词
所以 apple 不能算“逐级构建”

因此 DFS 时，根节点的孩子必须是完整单词才能继续。每深入一层，都相当于确认一个更长前缀确实存在于列表中。

三、用例子走 DFS 更新答案

假设词典为 [w, wo, wor, worl, world, banana]。Trie 建好后，从根出发只能进入 w，因为 b 不是完整单词。进入 w 后继续检查 wo、wor、worl、world。

root
├─ w(word=w)
│  └─ o(word=wo)
│     └─ r(word=wor)
│        └─ l(word=worl)
│           └─ d(word=world)
└─ b
   └─ a
      └─ n...

合法 DFS 路径只走 word != null 的节点
答案最终更新为 world

如果同时有 apple 和 apply，长度相同，题目通常要求字典序最小。按 a 到 z 顺序 DFS 可以自然先遇到字典序小的词，也可以在更新答案时显式比较。

四、和排序 + 哈希表的对比

这题也可以用哈希表：把所有单词放入 set，然后对每个单词检查它的所有前缀是否都在 set 中。若单词平均长度为 L，单词数为 N，检查前缀可能是 O(N*L^2)，因为构造子串也有成本。

方案	思路	时间特点	优点
哈希表	枚举每个单词的所有前缀	简单但可能频繁构造字符串	代码短
Trie	路径上只走完整前缀节点	总字符级遍历	前缀关系直观
排序 DP	按长度从短到长扩展	依赖 set 判断	易处理字典序

Trie 方案的教学价值更强，因为它直接把“前缀必须存在”翻译成“路径上每个节点必须是单词终点”。

五、字典序和答案更新规则

如果题目要求长度相同返回字典序最小，需要明确比较规则。答案更新通常写成：更长则替换；长度相同且字典序更小也替换。按 children[0..25] 顺序 DFS 可以减少一些显式比较，但显式比较更不容易依赖遍历细节。

void update(String w) {
    if (w.length() > ans.length()
        || (w.length() == ans.length() && w.compareTo(ans) < 0)) {
        ans = w;
    }
}

如果使用 Map 孩子，遍历顺序不稳定，更应该显式比较字典序。不要把哈希表或 HashMap 的迭代顺序当作字典序。

常见误区与追问

记忆钩子：路径存在不等于前缀单词存在，必须每一层都是 isEnd=true。

误区：只要单词在 Trie 里就合法。 还要它的每个短前缀都作为完整单词存在。
误区：节点存在就说明前缀存在。 节点存在只是路径存在，必须看 isEnd 或 word 标记。
误区：长度相同随便返回。 题目通常要求字典序最小，需要明确处理。
追问：能用哈希表做吗？ 能，枚举所有前缀查 set；Trie 更直观地表达前缀链。
追问：为什么根节点的孩子要特殊处理？ 根不代表单词，第一层字符也必须是完整单词才能继续。
追问：复杂度是多少？ 建 Trie 是总字符数级别，DFS 也至多访问 Trie 节点，整体约 O(S)。

加强记忆

所有前缀都存在的最长单词，可以记成“只走完整单词节点的 Trie DFS”。普通 Trie 路径只说明前缀被某个长词使用过，而本题要求每一级前缀本身都是词典单词，所以 DFS 必须在 isEnd=true 的孩子上继续。答案更新再处理长度和字典序。把这个题想成“从一层层台阶搭词”，每一级台阶都必须真实存在，就不会把路径存在误判成前缀合法。

简化版

详细版