文章目录
- 题目介绍
- 题解
题目介绍
题解
解析：
-
初始化：创建一棵 26 叉树，一开始只有一个根节点 root。26 叉树的每个节点包含一个长为 26 的儿子节点列表 son，以及一个布尔值 end，表示是否为终止节点。
-
insert：
- 遍历字符串 word，同时用一个变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。
- 如果 word[i] 不是 cur 的儿子，那么创建一个新的节点 node 作为 cur 的儿子。如果 word[i]=a，那么把 node 记录到 cur 的 son[0] 中。如果 word[i]=b，那么把 node 记录到 cur 的 son[1] 中。依此类推。
- 更新 cur 为儿子列表中的相应节点。
- 遍历结束，把 cur 的 end 标记为 true。
-
search 和 startsWith 可以复用同一个函数 find：
- 遍历字符串 word，同时用一个变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。
- 如果 word[i] 不是 cur 的儿子，返回 0。search 和 startsWith 收到 0 之后返回 false。
- 更新 cur 为儿子列表中的相应节点。
- 遍历结束，如果 cur 的 end 是 false，返回 1，否则返回 2。search 如果收到的是 2，返回 true，否则返回 false。startsWith 如果收到的是非 0 数字，返回 true，否则返回 false。
代码如下：
class Trie {public Trie() {}public class Node {Node son[]= new Node[26];// 创建一个可以存储 26 个 Node 对象的数组boolean end; // 表示是否为终止节点}Node root = new Node(); //只创建一次，所有的儿子共用一个根节点 public void insert(String word) {Node cur = root;for (char c : word.toCharArray()) {if (cur.son[c - 'a'] == null) {cur.son[c - 'a'] = new Node();}cur = cur.son[c - 'a'];}cur.end = true;}public boolean search(String word) {return find(word) == 2;}public boolean startsWith(String prefix) {return find(prefix) != 0;}public int find(String word) {Node cur = root;for (char c : word.toCharArray()) {if (cur.son[c - 'a'] == null) {return 0;}cur = cur.son[c - 'a'];}return cur.end == true ? 2 : 1;}
}/*** 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);*/
