Description
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Solution
Array Trie, insert time O(len), search time O(len), startsWith time O(len)
Reference: 小白详解 Trie 树
很多文章里将这种实现称为“标准 Trie 树”，但其实它只是 Trie 众多实现中的一种而已，由于这种实现结构简单，检索效率很好，作为讲解示例很不错，因此特地改称其为“经典 Trie 树”，这里引用一下别人家的示例图[2]：
abc、d、da、dda 四个字符串构成的 Trie 树，如果是字符串会在节点的尾部进行标记。没有后续字符的 branch 分支指向NULL
如上图，这种实现的特点是：每个节点都由指针数组存储，每个节点的所有子节点都位于一个数组之中，每个数组都是完全一样的。对于英文而言，每个数组有27个指针，其中一个作为词的终结符，另外 26 个依次代表字母表中的一个字母，对应指针指向下一个状态，若没有后续字符则指向NULL。由于数组取词的复杂度为O(1)，因此这种实现的 Trie 树效率非常的高，比如要在一个节点中写入字符“c”,则直接在相应数组的第三个位置标入状态即可，而要确定字母“b”是否在现有节点的子节点之中，检查子节点所在数组第二个元素是否为空即可，这种实现巧妙的利用了等长数组中元素位置和值的一一对应关系，完美的实现了了寻址、存值、取值的统一。
但其缺点也很明显，它强制要求链路每一层都要有一个数组，每个数组都必须等长，这在实际应用中会造成大多数的数组指针空置（从上图就可以看出），事实上，对于真实的词典而言，公共前缀相对于节点数量而言还是太少，这导致绝大多数节点下并没有太多子节点。而对于中文这样具有大量单字的语言，若采取这样的实现，空置指针的数量简直不可想象。因此，经典 Trie 树是一种典型的以“空间换时间”的实现方式。一般只是拿来用于课程设计和新手练习，很少实际应用。
class Trie {
private Node root;
/** Initialize your data structure here. */
public Trie() {
root = new Node();
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node pre = root;
for (int i = 0; i < word.length(); ++i) {
int index = word.charAt(i) - 'a';
if (pre.next[index] == null) {
pre.next[index] = new Node();
}
pre = pre.next[index];
}
pre.isWord = true; // don't forget
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node node = find(word);
return node != null && node.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return find(prefix) != null;
}
private Node find(String word) {
Node pre = root;
for (int i = 0; i < word.length() && pre != null; ++i) {
pre = pre.next[word.charAt(i) - 'a'];
}
return pre;
}
class Node {
Node[] next;
boolean isWord;
public Node() {
next = new Node[26];
isWord = false;
}
}
}
/**
* 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);
*/
HashMap Trie
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) {
TrieNode pre = root;
for (int i = 0; i < word.length(); ++i) {
char c = word.charAt(i);
if (!pre.childrenMap.containsKey(c)) {
pre.childrenMap.put(c, new TrieNode(c));
}
pre = pre.childrenMap.get(c);
}
pre.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode pre = root;
for (int i = 0; i < word.length(); ++i) {
char c = word.charAt(i);
if (!pre.childrenMap.containsKey(c)) {
return false;
}
pre = pre.childrenMap.get(c);
}
return pre.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode pre = root;
for (int i = 0; i < prefix.length(); ++i) {
char c = prefix.charAt(i);
if (!pre.childrenMap.containsKey(c)) {
return false;
}
pre = pre.childrenMap.get(c);
}
return true;
}
class TrieNode {
char val;
Map<Character, TrieNode> childrenMap;
boolean isWord;
public TrieNode() {
val = ' ';
childrenMap = new HashMap<>();
}
public TrieNode(char val) {
this.val = val;
childrenMap = new HashMap<>();
}
}
}
/**
* 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);
*/
