题目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 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数总计不超过3 * 104次题解class Trie { // Trie节点 private static class TrieNode { TrieNode[] children; // 26个字母每个位置存子节点 boolean isEnd; // 是否是单词末尾 public TrieNode() { children new TrieNode[26]; // 默认全部null代表没有这个字母分支 isEnd false; } } private TrieNode root; // Trie() 初始化创建根节点 public Trie() { root new TrieNode(); } // insert插入单词 public void insert(String word) { TrieNode cur root; // 指针从根出发 for (char c : word.toCharArray()) { // 遍历单词每一个字符 int idx c - a; // a -0b-1 ... z-25 if (cur.children[idx] null) { // 当前节点没有这个字母分支新建节点 cur.children[idx] new TrieNode(); } cur cur.children[idx]; // 指针往下移动到子节点 } cur.isEnd true; // 单词走完标记结尾 } // search查找完整单词 public boolean search(String word) { TrieNode cur root; for (char c : word.toCharArray()) { int idx c - a; if (cur.children[idx] null) { // 中途分支断了单词不存在 return false; } cur cur.children[idx]; } // 字符全部走完还要判断是不是单词结尾 return cur.isEnd; } // startsWith判断是否有单词以prefix为前缀 public boolean startsWith(String prefix) { TrieNode cur root; for (char c : prefix.toCharArray()) { int idx c - a; if (cur.children[idx] null) { return false; } cur cur.children[idx]; } // 只要路径存在就可以不需要isEnd return true; } }