字典树Trie
字典树也叫前缀树，是一种在字符串查找，前缀匹配等问题广泛应用的算法，为什么使用字典树呢？我们都知道如果对于一个存储有n个条目的数据集做查询，线性结构的时间复杂度是O(n)，这是相当恐怖的，改进的基于红黑树的查询时间复杂度是O(logn)，虽然已经好很多，但是当n非常大时，这个时间复杂度还是不能接受的。而字典树能做到查询的时间复杂度和数据集存储的数目n无关，而仅和被查询的字符串长度有关，所以它在查找时只有O(1)的时间复杂度。这是怎么做到的呢，其实很简单，下图是某存储英文的字典树的结构：
Trie
该树中存储了英语单词，如果要查询某个单词，比如
，只需要先找到w，再找到i、n、d即可。可见对每个单词的查找只需要查找单词长度次，而且每次查找只需查找26次之内（即便算上大写也在52次之内）。
Trie数据结构设计要点：
- 添加操作：从根开始向下，如果某个节点没有则拓展一个新节点，添加完毕后在最后一个节点处将标志置true；
- 查询操作：基本过程与插入相同，向下查找，如果中间遇到一次节点不存在，直接返回false，一直向下查找，最终返回标志位；
- 每遍历到一个叶子节点，就查到一个单词（条目）；
- 可能某个单词是其它单词的前缀，如果没到叶子节点就存储了一个单词，则将此处标志置true。
字典树的实现
首先考虑节点结构，并假设这里的节点仅存储小写英文单词，故每个节点下应该有26个分支（实际如何存储根据具体情境）：
class Node{
char c;
Node next[26];//指向下一个节点
}
不过由于在寻找下一个节点时，我们实际上已经知道了要找哪个，故可以将当前节点和和其指向的节点存储为一个整体（相当于存储是在边上），故节点设计为：
class Node{
boolean isWord;
Map<char,Node> next;
}
其中isWord用于标识单词结尾，从而Trie类：
import java.util.TreeMap;
public class Trie {//不需要泛型，这里仅解决字符串类问题
private class Node{//Trie的节点类
public boolean isWord;
public TreeMap<Character,Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(false);//表示使用上面的构造函数
}
}
private Node root;
private int size;
public Trie(){
root = new Node();
size = 0;
}
//获取Trie中的单词数量
public int getSize(){
return size;
}
//向Trie中添加新单词(字符串)
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)//如果映射中没有包含到c的映射
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if (!cur.isWord) {//首先检查该单词是否已经存在
cur.isWord = true;
//此时来到了当前添加单词的最后节点，但不一定是叶子节点，因为可能是别的单词前缀
size++;
}
}//作业：使用递归写法完成添加操作
public boolean contains(String word){
//查询单词word是否在Trie中
Node cur = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return cur.isWord;
}//作业，递归写法
//其实Trie也是一个集合
public boolean isPrefix(String prefix){
//查询Trie中是否有单词以prefix为前缀(一个单词也是本身的前缀)
Node cur = root;
for(int i=0;i<prefix.length();i++){
char c = prefix.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;//和查询单词操作类似，不过无需检查是否包含单词
//作业：BSTSet中查询前缀
}
}
可以看到，Trie类的实现我们借助了TreeMap等底层数据结构，这正是数据结构的魅力，就像乐高积木一样，由一些基础的木块一步步搭建出美丽的艺术品。
Trie的应用——LeetCode207、211
LeetCode207不再介绍，就是设计一个字典树类，支持添加和查找操作，上面实现的类修改下类名即可。
LeetCode211
LeetCode211
这个题目其实和Trie类要完成的工作类似，不过加入了一些更灵活的条件（简易正则表达式），只需对我们的Trie类做小部分修改即可：
import java.util.TreeMap;
class WordDictionary {
private class Node{//Trie的节点类
public boolean isWord;
public TreeMap<Character,Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(false);//表示使用上面的构造函数
}
}
private Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
public void addWord(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)//如果映射中没有包含到c的映射
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if (!cur.isWord) //首先检查该单词是否已经存在
cur.isWord = true;
}
public boolean search(String word) {
return match(root, word,0);
}
private boolean match(Node node, String word, int index) {
//从index处开始匹配
if (index == word.length())
return node.isWord;//递归终止条件,word匹配完毕,若为true则返回匹配成功,false匹配失败
char c = word.charAt(index);
if (c == '.') {
for (char nextChar : node.next.keySet()) {//是.则遍历所有字母
if (match(node.next.get(nextChar), word, index + 1))
return true;
}
return false;
} else {
if (node.next.get(c) == null)
return false;
return match(node.next.get(c), word, index + 1);//继续匹配后面的部分
}
}
}
可以发现，我们只对查询函数做了改动，而查询主要是基于递归实现的。
