字典树

先来膜拜一下三叶姐的代码。
https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247488490&idx=1&sn=db2998cb0e5f08684ee1b6009b974089&chksm=fd9cb8f5caeb31e3f7f67dba981d8d01a24e26c93ead5491edb521c988adc0798d8acb6f9e9d&scene=178&cur_album_id=1783678230541975556#rd

Trie 类：

• Trie() 初始化前缀树对象。

• void insert(String word) 向前缀树中插入字符串 word 。

• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

• insert、search 和 startsWith 调用次数 总计 不超过 3 * 次

Trie 树

Trie 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

类似这样我们取两个单词abcde,defee（瞎拼的单词）制作字典树，蓝色块是两个单词共同用到的单词。理论上二维数组最多需要26*26个存储单元来存储对象。我们用链表来实现占用空间更小。

链表图示：

ps。一般不用数组实现这种功能，使用数组时，二维数组存储的是累计第几个字母，每次变量p为最后一个字母标号处。

力扣链接：

208. 实现 Trie (前缀树)