Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert(“apple”);trie.search(“apple”); // returns truetrie.search(“app”); // returns falsetrie.startsWith(“app”); // returns truetrie.insert(“app”); trie.search(“app”); // returns trueNote:
You may assume that all inputs are consist of lowercase letters a-z.All inputs are guaranteed to be non-empty strings.
难度：medium
题目：实现 Trie 树（字典树），插入，搜索和前缀方法。你可以假定所有的输入都是小写字母，所有输入都是非空 (not empty) 字符串。
Runtime: 89 ms, faster than 98.80% of Java online submissions for Implement Trie (Prefix Tree).
class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
char c = word.charAt(0);
int i = 0, idx = 0;
TrieNode ptr = root;
for (; i < word.length(); i++, ptr = ptr.next[idx]) {
idx = word.charAt(i) – ‘a’;
if (null == ptr.next[idx]) {
ptr.next[idx] = new TrieNode();
}
}
ptr.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
char c = word.charAt(0);
int i = 0, idx = 0;
TrieNode ptr = root;
for (; i < word.length() – 1; i++, ptr = ptr.next[idx]) {
idx = word.charAt(i) – ‘a’;
if (null == ptr.next[idx]) {
return false;
}
}
TrieNode end = ptr.next[word.charAt(i) – ‘a’];
return end != null && end.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
int idx = 0, i = 0;
TrieNode ptr = root;
for (; i < prefix.length(); i++, ptr = ptr.next[idx]) {
idx = prefix.charAt(i) – ‘a’;
if (null == ptr.next[idx]) {
return false;
}
}
return i >= prefix.length();
}
public static class TrieNode {
public boolean isWord;
public TrieNode[] next = new TrieNode[26];
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/