字典树

字典树是一种由字符串字符构建的树形结构，从根节点到标记节点的每条路径都拼成一个单词。当需要在大规模字符串集合中进行快速前缀查询时，它是合适的数据结构。哈希映射可以检查整个单词是否存在，而字典树可以在 O(长度) 时间内检查字典中是否存在以给定前缀开头的单词。本阶段的三个问题涵盖了构建字典树、通配符搜索以及利用字典树剪枝网格搜索，共同覆盖了面试中字典树应用的全范围。