Implement Trie (Prefix Tree)
实现一个trie. 这个需要注意每个方法的复杂度.
class TrieNode {
public boolean endPoint;
public TrieNode[] next;
public TrieNode() {
endPoint = false;
next = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if(word != null) {
TrieNode tmp = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(tmp.next[c-'a'] == null)
tmp.next[c-'a'] = new TrieNode();
tmp = tmp.next[c-'a'];
}
tmp.endPoint = true;
}
}
// Returns if the word is in the trie.
public boolean search(String word) {
if(word == null)
return false;
TrieNode tmp = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(tmp.next[c-'a'] == null)
return false;
else
tmp = tmp.next[c-'a'];
}
return tmp.endPoint;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if(prefix == null)
return false;
TrieNode tmp = root;
for(int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if(tmp.next[c-'a'] == null)
return false;
else
tmp = tmp.next[c-'a'];
}
return true;
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");