预计阅读时间：2 分钟

字典树

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

基础

leetcode 208

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

leetcode 648

对每个单词找最短的词根前缀。沿树下行，一碰到 is_end 就停——最先命中的就是最短前缀。

leetcode 1233

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

leetcode 1268

建字典树后，对每个前缀 dfs 找字典序最小的三个单词即可，dfs 的复杂度取决于 products[i] 的长度，3000×1000 的规模能过。

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

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

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