字典树

前缀树(trie)是一种由字符串字符构建的树结构，其中从根到标记节点的每条路径拼出一个单词。当你需要在大规模字符串集合中进行快速前缀查找时，这是正确的数据结构。哈希表可以检查整个单词是否存在，但前缀树可以在O(长度)时间内检查字典中是否有任何单词以给定前缀开头。本阶段的三个问题涵盖了构建前缀树、使用通配符搜索以及使用前缀树剪枝网格搜索，这些共同覆盖了面试中前缀树应用的全部范围。