Trie
Trie.java 源码
package datastructure.tree.leetcode;
/**
* @author roseduan
* @time 2020/10/25 11:11 上午
* @description 实现一个字典树
*/
public class Trie {
private static final int SIZE = 26;
private boolean end;
private final Trie[] children;
/** Initialize your data structure here. */
public Trie() {
this.end = false;
this.children = new Trie[SIZE];
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie p = this;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new Trie();
}
p = p.children[c - 'a'];
}
p.end = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie p = this;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
return false;
}
p = p.children[c - 'a'];
}
return p.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Trie p = this;
for (char c : prefix.toCharArray()) {
if (p.children[c - 'a'] == null) {
return false;
}
p = p.children[c - 'a'];
}
return true;
}
}
你可能感兴趣的文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
8、 golang
-
9、 openharmony
-
10、 Vue中input框自动聚焦