预计阅读时间：3 分钟

字典树

字典树（Trie）是前缀匹配的专用兵装：把一堆字符串挂在同一棵树上，前缀问题就变成了从根往下走的问题。本合集收录字典树题目。

基础

leetcode 208

模板题。唯一容易漏的点：节点上要挂 is_end 标记单词结束，否则「前缀存在」和「单词存在」区分不开。

leetcode 648

对每个单词找最短的词根前缀。沿树下行，一碰到 is_end 就停——最先命中的就是最短前缀；走不下去也没碰到 is_end，就保留原词。

leetcode 1233

要求输出所有最顶级的父文件夹。坑在 / 的特判：前缀匹配上不代表就是父文件夹，/a/b 是 /a 的子文件夹，但 /ab 不是——匹配结束后下一位是 / 的才算。

leetcode 1268

建字典树后，对每个前缀 dfs 找字典序最小的三个单词即可：dfs 按 a 到 z 的顺序走，凑满 3 个立即停。最坏情况下每次 dfs 也只走遍前缀对应的子树，而题目保证所有 products[i] 的总长 ≤ $2 \cdot 10^4$（字典树节点数不超过它），searchWord 长度 ≤ 1000，总量在 $2 \cdot 10^7$ 以内，能过。某个前缀在树里走不到时，后面所有前缀的答案都是空列表。

进阶优化：先把 products 排序再插入，插入即按字典序进行，于是可以在建树时就把每个节点的前三个推荐预存在节点上。这样遍历 searchWord 时每一步 $O(1)$ 拿答案，products[i] 和 searchWord 长度到 $10^5$ 的规模也能做。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。