来自腾讯二面555。
前缀树
子树有规律的多叉树
定义
其实就是26叉树。
操作
1，add
- 从根开始搜索字符相应的子节点。
- 如果子节点存在，则继续搜索下一个字符对应的子节点。
- 如果子节点不存在，则创建对应子节点。
- 循环上述过程。
2，update
- 从根开始搜索字符相应的子节点。
- 如果子节点存在，则继续搜索下一个字符对应的子节点。
- 如果子节点不存在，则返回false。
- 循环上述过程，到最后返回true。
代码
代码语言：javascript复制class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
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;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private 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;
}
}就这。
