题目介绍
题解
解析：
初始化：创建一棵 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);
*/