1.字典树：

为字典设计的数据结构，专门处理字符串。
假如通讯录里面有很多人，要想快速查找的话，二分树以及各类排序算法实际上都不合适。
因此采用字典树结构

2.字典树结构：

字典树的节点不止一个，对于英语来说，每个节点有26个指向下面节点的指针，我们可以不用保留节点本身的值。

  1. class Node{
  2.     private char val;
  3.     private Map<char, Node> next;
  4. }
  5. // 定义Node

但是对于进行遍历时，需要查看是否为单词，例如 pan / panda, 因此需要加入 isWord 判定在该节点时，是否为end。

  1. // 定义 Node
  2. class Node{
  3.     private isWord;
  4.     private Map<char, Node> next;
  6.     public Node(Boolean isWord){
  7.         this.isWord = isWord;
  8.     }
  10.     public Node(){
  11.         this(null);
  12.     }
  13. }

3.具体实现

  1. //实现字典树
  2. public class Trie{
  3.     class Node{
  4.         private isWord;
  5.         private Map<char, Node> next;
  7.         public Node(Boolean isWord){
  8.             this.isWord = isWord;
  9.             next = new TreeMap<>();
  10.         }
  12.         public Node(){
  13.             this(null);
  14.         }
  15.     }
  16.     private Node root;
  17.     private int size;
  19.     public Trie(){
  20.         root = null;
  21.         size = 0;
  22.     }
  23.     // 添加单词
  24.     public void add(String word){
  25.         if(word == null) return false;
  26.         Node cur = root;
  27.         for(int i = 0; i < word.length(); i++){
  28.             char c = word.charAt(i);
  29.             if(cur.next.get(c) == null){
  30.                 cur.next.put(c, new Node());
  31.             }
  32.             cur = cur.next.get(c);
  33.         }
  34.         if(!cur.isWord){
  35.             cur.isWord = true;
  36.             size++;
  37.         } 
  38.     }
  40.     // 查询单词
  41.     public boolean has_word(String word){
  42.         if(word == null) return false;
  43.         Node cur = root;
  44.         for(int i = 0; i < word.length(); i++){
  45.                char c = word.charAt(i);
  46.             if(cur.next.get(c) == null){
  47.                 return false;
  48.             }
  49.             cur = cur.next.get(c);
  50.         }
  51.         // 传入 panda 为单词，但是 Pan未传入，不能算作单词
  52.         return cur.isWord;
  53.     }
  54. }

4.优化：添加前缀查询

  1. public boolean isPrefix(String prefix){
  2.     if(prefix == null) return false;
  3.         Node cur = root;
  4.         for(int i = 0; i <prefix.length(); i++){
  5.                char c = prefix.charAt(i);
  6.             if(cur.next.get(c) == null){
  7.                 return false;
  8.             }
  9.             cur = cur.next.get(c);
  10.         }
  11.     return true;
  12. }

5.相关问题：

leetcode 208
leetcode 211

6.相关优化：

将每个节点不再只是一个字符，而是可以保存一个单词。
压缩字典树 / 字串查询 / 模式匹配问题