208
Implement Trie (Prefix Tree)
24.9%
Medium
class TrieNode {
// Initialize your data structure here.
public TrieNode[] childNode;
public int freq;
public TrieNode() {
childNode = new TrieNode[26];
int freq = 0;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
insertHelper(word,root);
}
private void insertHelper(String word, TrieNode node){
if (word.length()==0) return;
int k = word.charAt(0) - 'a';
if (node.childNode[k] == null) node.childNode[k] = new TrieNode();
if (word.length() == 1) node.childNode[k].freq++;
insertHelper(word.substring(1), node.childNode[k]);
}
// Returns if the word is in the trie.
public boolean search(String word) {
return searchHelper(word, root);
}
private boolean searchHelper(String word, TrieNode node){
if (word.length()==0){
if (node.freq>0) return true;
return false;
}
int k = word.charAt(0) - 'a';
if (node.childNode[k] == null) return false;
return searchHelper(word.substring(1), node.childNode[k]);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
return startWithHelper(prefix, root);
}
private boolean startWithHelper(String word, TrieNode node){
if (word.length()==0) return true;
int k = word.charAt(0) - 'a';
if (node.childNode[k] == null) return false;
return startWithHelper(word.substring(1), node.childNode[k]);
}
}