标签
设计
数组
字符串
日期
Oct 28, 2022
剑指 Offer II 062. 实现前缀树
题目描述
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。
void insert(String word)向前缀树中插入字符串word。
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
题目解析
思路：
- 使用一个大小为26的数组存储字符串中的字母，isEnd表示当前字符是否是字符串的结尾
- 插入的时候初始化一个Trie，依次处理各个字符，存在的话即跳到下一个字符，不存在的话则创建一个，直到最后一个字符，并使用isEnd标识它是最后一个节点
- 查找方法则是遍历查看其各个字符是否在其节点中，并且其末尾字符的isEnd标识是true
- 查找前缀只需遍历该前缀的各个字符查看其各个字符是否在其节点中即可