前缀树
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
前缀树
特点
前缀树的查找效率高于哈希数组，但是空间消耗要大于哈希数组
实现
class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.node[c-'a']==null){
node.node[c-'a'] = new TrieNode();
}
node = node.node[c-'a'];
}
node.item = word;//保存当前叶子结点对应的字符串
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c:word.toCharArray()){
if(node.node[c-'a']!=null)
node = node.node[c-'a'];
else
return false;
}
return word.equals(node.item);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
if(node.node[c-'a']!=null)
node = node.node[c-'a'];
else
return false;
}
return true;
}
}
class TrieNode{
TrieNode []node;
String item;
public TrieNode(){
node = new TrieNode[26];
item = "";
}
}
总结
前缀树是字符串笔试中经常会使用到的存储数据结构，要熟练前缀树的创建与使用。
