从零学算法208
208.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 次
- 定义树中每个节点包含子节点数组，记录下一个字符的所有可能性，对该题而言只可能为 26 个字符中的一个，所以初始化时长度为 26 即可，再添加一个变量 isEnd 记录当前节点对应的字符是否为某个单词的尾字符，就能满足 search 函数的需求。(这里当前节点对应的字符，其实被隐含在它属于父节点的子节点数组中第几位，具体看代码)
- 插入字符串时，遍历它，只要当前字符不在树的这一层的可能性中，就加入该可能，否则就直接去往下一层，等待判断下一个字符是否在下一层。
- 比如字符串 abc 被插入，我们用数组层数表示树的层数，会得到
[a,[b,[c]]]，并且 c 为某个字符串结尾，再插入 ade 会得到[a,[b,d,[c,e]]]，并且 e 也为某个字符串结尾 - 这样比如判断是否包含前缀 ab，我们就先看第一层是否包含 a，然后去下一层看是否包含 b
- 而判断是否包含某个完整的字符，在 insert 完一个单词后，我们会在树中对应那层的那个节点记录状态为 isEnd，表示是某个单词的结尾，调用 search 时遍历到这一层的这个节点时判断 isEnd 即可
-
class Trie {// 记录下一位可能的字符Trie[] children;boolean isEnd;public Trie() {this.children = new Trie[26];this.isEnd = false;}public void insert(String word) {// 获取根节点Trie node = this;for(char ch:word.toCharArray()){// 获取当前字符对应下标int index = ch-'a';// 如果未记录就记录当前字符并为该节点新建一个字典树if(node.children[index] == null)node.children[index] = new Trie();// 移动到下一个节点去记录包含字母的可能性// 移动后的此时的 node 对应字符 ch，因为它是父节点的第 index 个子节点// index 为 0 对应字符 'a'，1对应 'b'... 25 对应 'z'node = node.children[index];}node.isEnd = true;}public boolean startsWith(String prefix) {Trie node = this;// 按顺序寻找树中是否存在一条遍历路径，从头开始包含 prefix 的每个字符for(char c:prefix.toCharArray()){int index = c-'a';// 只要有一个字符不被包含在可能的下一个字符，就表示不存在该前缀if(node.children[index] == null)return false;// 存在就继续验证下个字符是否依旧存在node = node.children[index];}return true;}// 相较于 startsWith 就是多了一个 isEnd 的验证public boolean search(String word) {Trie node = this;for(char c:word.toCharArray()){int index = c-'a';if(node.children[index] == null)return false;node = node.children[index];}// 如果最后的字符是尾字符才表示树中包含 word// 但是这不代表这个字符就不能有后面的字符了，只是对于某个单词而言是尾字符return node.isEnd;}}/*** 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);*/