Trie:字典树（是一棵树，存放一个个字符串），是多叉树（几查不确定），遍历的次数与单词的长度相关，如下图：每一列代表一个单词，单词长度是多少，则需要遍历多少次
Trie：也叫前缀树
Tire定义主要有三个方法，增加单词，是否包含单词，是否包含前缀，具体实现如下：
package trie;
import java.util.TreeMap;
public class Trie {
private class Node{
public boolean isWord;
public TreeMap<Character, Node> next;
//创建的每个Node，都会包含一个新建的TreeMap,通过该map中的key寻找它会指向哪些Node（同时，该key也是整个要处理的单词中的一个字符)
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中添加一个新的单词word
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)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if(!cur.isWord){
cur.isWord = true;
size ++;
}
}
// 查询单词word是否在Trie中
public boolean contains(String word){
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中有单词以prefix为前缀
public boolean isPrefix(String 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;
}
}
具体问题：判断一个字符串集合中是否含有正则表达式代表的单词，实现如下(Trie和集合)：
package trie;
import java.util.TreeMap;
public class WordDictionary {
private class Node{
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;
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)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
cur.isWord = true;
}
/*
* 判断是否包含某个正则表达式所表示的单词，正则表达式中的特殊字符只能有"."整个字符来代表任意字符
* 使用递归的形式进行遍历
* */
public boolean search(String word) {
return match(root, word, 0);
}
//私有的递归调用的函数
private boolean match(Node node, String word, int index){
//终止条件：遍历到最后一个字符，则返回是否包含：如果最后一个字符是单词结尾，则返回true,否则返回false
if(index == word.length())
return node.isWord;
char c = word.charAt(index);
//如果不是"."的情况下，
// 不包含当前字符，则直接返回fasle；包含该字符则继续递归
if(c != '.'){
//node.next得到当前节点中的map，如果map.get(c)说明当前节点对应的字符和当前遍历的字符相等，可以进行下一次遍历
//注意node.next对应的是当前节点中存储的map，
// 而node.next.get(c)对应的是下一个新的节点，同时能够代表当前节点是否对应字符c
if(node.next.get(c) == null)
return false;
return match(node.next.get(c), word, index + 1);
}
else{//如果当前字符是"."的情况下，需要遍历后续的所有节点
for(char nextChar: node.next.keySet())
//如果其中任意一个节点匹配单词成功（注意代表的是单词，不是字符），则返回true
if(match(node.next.get(nextChar), word, index + 1))
return true;
//如果遍历完"."后所有分支的节点，没有任何一个节点匹配单词成功，则返回false
return false;
}
}
public static void main(String[] args) {
WordDictionary wd = new WordDictionary();
wd.addWord("a");
wd.addWord("ab");
wd.addWord("ac");
System.out.println(wd.search("ad"));
}
}
求前缀为某个字符串的单词的值的和（Trie和映射map）：
package trie;
import java.util.TreeMap;
public class MapSum {
private class Node{
public int value;
public TreeMap<Character, Node> next;
public Node(int value){
this.value = value;
next = new TreeMap<>();
}
public Node(){
this(0);
}
}
private Node root;
public MapSum() {
root = new Node();
}
public void insert(String key, int val) {
Node cur = root;
for(int i = 0 ; i < key.length() ; i ++){
char c = key.charAt(i);
if(cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
cur.value = val;
}
/*
* 求前缀为prifix的所有单词的值的和
* 1、找到前缀为prifix的最后一个字符对应的节点的位置
* 2、从该节点开始，遍历所有子节点值相加
* */
public int sum(String prefix) {
Node cur = root;
//找前缀为prifix的最后一个字符对应的节点的位置
for(int i = 0 ; i < prefix.length() ; i ++){
char c = prefix.charAt(i);
if(cur.next.get(c) == null)
return 0;
cur = cur.next.get(c);
}
//从当前节点开始，所有子节点的值求和
return sum(cur);
}
//从当前节点开始，所有子节点的值求和
private int sum(Node node){
//此处相当于前序遍历：先遍历当前节点，再遍历子节点
int res = node.value;
for(char c: node.next.keySet())
res += sum(node.next.get(c));
return res;
}
}