Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
思路：
定义一个节点表示TrieNode，由于题目说明只有a-z，因此子节点用一个26长度的数组即可，此外用一个bool变量表示到当前节点为止是否为一个单词。
public class GJ_TrieTree {
class TrieNode {
public char c;
public TrieNode[] children;
public boolean isWord;
public TrieNode(char c) {
this.c = c;
this.children = new TrieNode[256];
this.isWord = false;
}
}
public TrieNode root;
/** Initialize your data structure here. */
public Trie() {
this.root = new TrieNode('0');
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode dummy = this.root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (dummy.children[c] == null) {
dummy.children[c] = new TrieNode(c);
}
dummy = dummy.children[c];
}
dummy.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode res = this.findHelper(word);
return (res != null && res.isWord);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return (this.findHelper(prefix) != null);
}
private TrieNode findHelper(String str) {
TrieNode dummy = this.root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (dummy.children[c] == null) {
return null;
}
dummy = dummy.children[c];
}
return dummy;
}
}
