字典树

一句话：字典树（Trie）是”用公共前缀换空间和查询效率”的哈希表替代品——当查询模式是”前缀匹配”而不是”精确匹配”时，哈希表无能为力（它只能判断整个字符串是否存在），字典树天然适合。

为什么哈希表解决不了前缀查询

208-实现Trie、648-单词替换、677-键值映射 的共同需求是**“是否存在以某个前缀开头的字符串”或”找出所有以某前缀开头的字符串”**——哈希表把整个字符串当作一个不可分割的键，只能回答”这个完整字符串在不在”，无法回答”有没有字符串以它开头”。

字典树把字符串拆成逐字符的路径：每个节点代表”到目前为止匹配的前缀”，从根走到某节点所经过的路径拼起来就是该节点对应的前缀。查询前缀是否存在，只需要沿着字符路径走能否走到底，不需要遍历所有字符串——这是字典树相对哈希表的核心优势，也是它存在的全部理由。

720-词典中最长的单词 进一步利用了这个结构：要求”由词典中逐字符添加能拼出的最长单词”，本质是在字典树上做一次 DFS/BFS，只走”每个前缀本身也是一个完整单词”的路径——如果某个前缀本身不是词典里的单词，这条路径就是断的，不需要继续往下探。

空间换查询效率的代价

211-添加与搜索单词 要求支持通配符 .（匹配任意字符）查询，这是字典树最能体现优势的场景：遇到 . 时在当前节点的所有子节点分支上做 DFS，普通哈希表完全没有类似的能力——它要么遍历全部字符串暴力匹配，要么根本无法支持。

代价是空间：每个字典树节点通常要为字母表的每个字符预留一个子节点指针（哪怕大多数是空的），比哈希表存储同样数量的字符串要占用更多内存。212-单词搜索II 把字典树和二维网格 DFS 结合，用字典树代替”每次都重新对候选单词做前缀匹配”，把整体复杂度从”单词数 × 网格搜索”降到”网格搜索时顺带在字典树上剪枝”——如果当前路径在字典树上已经找不到子节点，就不需要继续往下搜索，这是字典树在这里承担的剪枝作用。