1.9 KiB
1.9 KiB
前缀树问题
截止目前（2020-02-04） 前缀树（字典树） 在 LeetCode 一共有 17 道题目。其中 2 道简单，8 个中等，7 个困难。
这里总结了四道题，弄懂这几道， 那么前缀树对你应该不是大问题， 希望这个专题可以帮到正在学习前缀树 的你。
前缀树的 api 主要有以下几个：
insert(word): 插入一个单词search(word)：查找一个单词是否存在startWith(word)： 查找是否存在以 word 为前缀的单词
其中 startWith 是前缀树最核心的用法，其名称前缀树就从这里而来。大家可以先拿 208 题开始，熟悉一下前缀树，然后再尝试别的题目。
一个前缀树大概是这个样子：
如图每一个节点存储一个字符，然后外加一个控制信息表示是否是单词结尾，实际使用过程可能会有细微差别，不过变化不大。
以下是本专题的四道题目的题解，内容会持续更新，感谢你的关注～