Implement Trie (Prefix Tree)
Total Accepted: 34060 Total Submissions: 134340 Difficulty: Medium
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
思路
class TrieNode {
int value;
TrieNode[] next = new TrieNode[26];
public TrieNode() {
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
insert(word, 1, 0, root);
}
public TrieNode insert(String word, int val, int index, TrieNode root) {
if (root == null) {
root = new TrieNode();
}
if (index == word.length()) {
root.value = val;
return root;
}
int c = word.charAt(index) - 'a';
root.next[c] = insert(word, val, index + 1, root.next[c]);
return root;
}
public boolean search(String word) {
return search(word, root, 0) != 0;
}
public int search(String word, TrieNode root, int index) {
if (root == null) {
return 0;
}
if (index == word.length()) {
if (root.value != 0) {
return root.value;
} else {
return 0;
}
}
int c = word.charAt(index) - 'a';
return search(word, root.next[c], index + 1);
}
public boolean startsWith(String prefix) {
return startsWith(prefix, root, 0);
}
public boolean startsWith(String prefix, TrieNode root, int index) {
if (root == null) {
return false;
}
if (index == prefix.length()) {
if (root != null) {
return true;
} else {
return false;
}
}
int c = prefix.charAt(index) - 'a';
return startsWith(prefix, root.next[c], index + 1);
}
}