class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode r = root;
for (int i = 0; i < word.length(); i++) {
int pos = word.charAt(i) - 'a';
if (r.next[pos] == null) r.next[pos] = new TrieNode();
r = r.next[pos];
}
r.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode r = root;
for (int i = 0; i < word.length(); i++) {
int pos = word.charAt(i) - 'a';
if (r.next[pos] == null) return false;
r = r.next[pos];
}
return r.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode r = root;
for (int i = 0; i < prefix.length(); i++) {
int pos = prefix.charAt(i) - 'a';
if (r.next[pos] == null) return false;
r = r.next[pos];
}
// prefix is word
if (r.isWord) return true;
// iterate next[]
for (TrieNode t : r.next) {
if (t != null) return true;
}
return false;
}
}
class TrieNode {
TrieNode[] next;
boolean isWord;
public TrieNode() {
next = new TrieNode[26];
}
}
public void insert(String word, int index) {
if (index == word.length()) {
this.hasWord = true;
return;
}
int pos = word.charAt(index) - 'a';
if (children[pos] == null) children[pos] = new TrieNode();
children[pos].insert(word, index+1);
}
