如何用字典树实现前缀匹配和自动补全（搜索提示）？

简化版

自动补全 = 「前缀定位 + 收集后缀」两步：先沿着用户输入的前缀在 Trie 里走到前缀末尾的那个节点（O(L)）；再从这个节点出发做 DFS，收集它子树里所有 isEnd 的单词，就是所有以该前缀开头的候选词。想要「最热门的补全」，可以在节点上额外存词频/权重，用堆取 Top K。

详细版

分两步：

List<String> autocomplete(String prefix) {
    List<String> res = new ArrayList<>();
    Trie node = find(prefix);        // 1. 走到前缀末尾节点，O(L)
    if (node == null) return res;    // 没有以此为前缀的词
    dfs(node, prefix, res);          // 2. 从该节点收集整棵子树的单词
    return res;
}
void dfs(Trie node, String cur, List<String> res) {
    if (node.isEnd) res.add(cur);    // 到达一个完整单词
    for (char c = 'a'; c <= 'z'; c++) {
        Trie child = node.children[c - 'a'];
        if (child != null) dfs(child, cur + c, res); // 按字母序递归
    }
}

第一步 O(L)：定位前缀。
第二步：遍历子树，收集所有单词。因为按 a→z 顺序 DFS，结果天然按字典序排列。
若前缀路径走不通，说明没有任何词以它开头，返回空。

完整版教学

一、为什么 Trie 天生适合自动补全

自动补全的需求是「给我所有以 app 开头的词」。哈希表把字符串打散了，做不到；而 Trie 把公共前缀存成了一条共享路径——所有以 app 开头的词，都在 app 那个节点的子树里。所以只要定位到前缀节点，它的整棵子树就是答案集合。这种「前缀 = 子树」的对应关系，是 Trie 相对哈希最有价值的能力。

二、第一步：定位前缀节点

和 startsWith 一样，沿着前缀的字符逐个下降。走到前缀最后一个字符对应的节点，就站在了「所有候选词的公共祖先」上。如果中途走不通，说明集合里没有任何词以这个前缀开头，直接返回空列表。这一步是 O(L)。

三、第二步：DFS 收集子树里的所有单词

站在前缀节点上，对它的子树做深度优先遍历，一路把字符拼进 cur：

每遇到一个 isEnd=true 的节点，就说明 cur 是一个完整单词，加入结果。
继续往下递归，直到把子树里所有单词都收集完。

按 a→z 的顺序递归，结果自然是字典序的，不用额外排序。这一步的耗时和「候选词的总字符数」成正比。

四、要「最相关/最热门」的补全怎么办

真实搜索框的补全不是列出全部，而是给最热门的几个。做法是在 Trie 节点上附加信息：

在每个 isEnd 节点存一个词频/搜索热度权重。
收集候选时，用一个大小为 K 的堆按权重维护 Top K 热门词。
或者在每个节点缓存「其子树里 Top K 高频词」，查询时直接读，避免每次遍历整棵子树。

这样就能做到「输入 app，优先提示 apple、application 等高频词」。

五、复杂度与工程考量

定位前缀：O(L)。
收集候选：O(子树里所有单词的总字符数)，最坏可能很大（前缀很短、匹配词很多）。
优化：限制返回数量（Top K）、节点缓存热门词、前缀太短时不触发补全。

工业级搜索提示还会结合拼写纠错、模糊匹配、个性化排序，但底层的「前缀定位 + 子树收集」就是 Trie 这套。

六、常见误区与追问

考点	正确口径
定位前缀	按字符走到前缀末尾节点
收集候选	从该节点 DFS/BFS 收集子树单词
排序推荐	按热度、字典序或时间排序

node = find(prefix)
if node == null: return []
dfs(node, prefix, result)
return top suggestions

自动补全分两步：先找到前缀节点，再在它的子树里找完整单词。

误区：每次补全都要扫描整个词库。 Trie 可以先 O(L) 定位前缀节点，再只遍历相关子树。
误区：找到前缀节点就等于找到一个完整单词。 前缀是否本身成词要看 isEnd，补全还要继续收集后代单词。
误区：搜索提示只按字典序就够。 工程中通常还要按热度、个性化、业务权重和安全过滤排序。
追问：候选太多怎么办？ 可在每个节点缓存 top N 热门词，查询时直接返回，更新时维护缓存。
追问：复杂度是多少？ 定位前缀 O(L)，收集候选取决于子树规模；若缓存 top N，可接近 O(L+N)。
追问：如何支持删除词？ 关闭单词终止标记并更新沿路径缓存，必要时清理无用节点。

七、加强记忆

Trie 自动补全 = 前缀定位（O(L)走到前缀末节点）+ 子树收集（DFS 找出该节点子树里所有 isEnd 单词），因为「前缀 = 子树」这一对应关系是哈希表给不了的。按 a→z 递归结果天然字典序。要「热门补全」就在节点存词频权重、用堆取 Top K 或缓存子树 Top K。前缀走不通即无候选。

简化版

详细版