208. 实现 Trie (前缀树)

---

208. 实现 Trie (前缀树)解析

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

一开始看到这个题，我就去看了题解（

主要是树已经忘记的差不多了，现在正在努力回忆中。。。，看见题解之后发现提示里面有一个

prefix.length <= 2000，？？？有什么单词是超过2000的吗？感觉这个就是纯粹在为了测试用例而测试用例，不说废话了，我在b站找到一个讲的很不错的视频，引用一下里面的图片

原地址：https://www.bilibili.com/video/BV1o64y1y7Qh?from=search&seid=15289883244640383003&spm_id_from=333.337.0.0

首先题目提示给了所有单词只有小写字母，那么所有字母有26个，我们可以用指针来映射一下这26个位置，使得来代表这26个字母，查询时指针如果指向的地方有数据，那么就表明这个英文字母存在，就可以使得指针继续往下走，直到要求查询的前缀或者单词到了最后一个元素为止，当需要插入的时候会先查询一个个字母是否存在映射，如果存在就会继续往下走，如果没有的话就会自己创建新的节点，然后继续执行判断，直到最后一个字母。

这两个图就很好的反应了本题的要求，那我们直接来看代码：

public class Trie {

​ private Trie[] children;
​ private boolean isEnd;

​ /** Initialize your data structure here. */
​ public Trie() {
​ // Trie前缀树(或者叫多叉单词查找数，字典树)

​ // 每个节点开辟26个存储空间，因为最多的情况下有a-z，26个英文字母在当前树中都构成了可能的前缀字母
​ children = new Trie[26];
​ // 初始化单词结尾标示为false
​ isEnd = false;
​ }

​ /** Inserts a word into the trie. */
​ public void insert(String word) {
​ // node指针指向当前对象的头结点
​ Trie node = this;
​ for(int i = 0; i < word.length(); ++i) {
​ char ch = word.charAt(i);
​ int index = ch - 'a';
​ if(node.children[index] == null) {
​ node.children[index] = new Trie();
​ }
​ node = node.children[index];
​ }
​ node.isEnd = true;
​ }

​ /** Returns if the word is in the trie. */
​ public boolean search(String word) {
​ // 调用前缀树遍历方法如果整个word遍历完了node还没指向空，并且正好指向一个isEnd标示为true说明当前单词存在
​ // 于前缀树中
​ Trie node = searchPrefix(word);
​ return node != null && node.isEnd;
​ }

​ /** Returns if there is any word in the trie that starts with the given prefix. */
​ public boolean startsWith(String prefix) {
​ // 调用前缀树遍历方法把prefix前缀单词装进去，如果最后返回的不是空指针说明前缀存在
​ return searchPrefix(prefix) != null;
​ }

​ // 查找单词是否存在于前缀树中遍历方法的封装
​ public Trie searchPrefix(String prefix) {
​ Trie node = this;
​ for(int i = 0; i < prefix.length(); ++i) {
​ char ch = prefix.charAt(i);
​ int index = ch - 'a';
​ if(node.children[index] == null) {
​ return null;
​ }
​ node = node.children[index];
​ }
​ return node;
​ }

}

/**

• Your Trie object will be instantiated and called as such:
• Trie obj = new Trie();
• obj.insert(word);
• boolean param_2 = obj.search(word);
• boolean param_3 = obj.startsWith(prefix);
*/

运行截图：

非常感谢提供解题方法的b站up主