字典树
又称前缀树，实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
public class T208Trie {
class TrieNode{
TrieNode []nodes;
boolean isLeaf;
int id;
public TrieNode(){
nodes=new TrieNode[26];
isLeaf=false;
id=0;
}
}
private TrieNode root;
public T208Trie() {
root=new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode tmpRoot=root;
int len=word.length();
for (int i = 0; i < len; i++) {
char c=word.charAt(i);
if(tmpRoot.nodes[c-'a']==null){
tmpRoot.nodes[c-'a']=new TrieNode();
}
tmpRoot=tmpRoot.nodes[c-'a'];
}
tmpRoot.isLeaf=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode tmpRoot=root;
int len=word.length();
for (int i = 0; i < len; i++) {
char c=word.charAt(i);
if(tmpRoot.nodes[c-'a']==null)return false;
tmpRoot=tmpRoot.nodes[c-'a'];
}
return tmpRoot.isLeaf;
}
public boolean startsWith(String prefix) {
TrieNode tmpRoot=root;
int len=prefix.length();
for (int i = 0; i < len; i++) {
char c=prefix.charAt(i);
if(tmpRoot.nodes[c-'a']==null)return false;
tmpRoot=tmpRoot.nodes[c-'a'];
}
return true;
}
public static void main(String[] args) {
T208Trie t208Trie=new T208Trie();
t208Trie.insert("hello");
System.out.println(t208Trie.search("hell")); // false
System.out.println(t208Trie.search("helloa")); // false
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 changzeyan@foxmail.com
