图片5.通过减少搜索空间，trie能够很好的完成boggle这个游戏
有很多其他的数据结构如，平衡树，hash表都能够在一个string的数据集中查找单词，但是我们为什么要使用trie呢？虽然hash表对于找到一个关键词（key）只需要
O
(1)的时间复杂度,但是在下列操作中，它就表现得不是很高效了。
找到拥有共同前缀的所有关键词（key）。
根据字典序枚举所有字符串
trie优于hash表的另外一个原因是，但hash表的数据规模扩大后，将会出现很多的hash碰撞，因此查询时间复杂度将会提高到 O (n), n 是插入的关键词的个数。而相比于hash表，trie在存储很多具有共同前缀的关键词时需要的空间更少。在这个例子里trie只需要 O (m)的时间复杂度（ m 是关键词的长度）。而在平衡树里查询一个关键词，则需要花费 O ( m log n )
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
}
复制代码
复杂度分析：
时间复杂度 O (m), m 是关键词的长度。在算法的每一次循环中，我们要么检查节点要么新建一个节点，直到该关键词的最后一个字母。所以，这只需要进行m次操作。
class Trie {
...
// search a prefix or whole key in trie and
// returns the node where search ends
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
}
复制代码
class Trie {
...
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}
复制代码
