Trie，又称前缀树或字典树。该树的每个节点包含以下字段：

  1. 指向子节点的指针数组children。
  2. 布尔字段isEnd

前缀树的每一条root节点到isEnd为true的节点路径为一个字符串。
前缀树有两个基础的操作：插入字符串和查询前缀。

208. 实现 Trie (前缀树) 难度：中等

  1. package com.linzhongkai.datastructure.tree;
  3. public class Trie {
  4.     private Trie[] children;
  5.     private boolean isEnd;
  6.     public Trie() {
  7.         children = new Trie[26]; //26个字母
  8.         isEnd = false;
  9.     }
  10.     public void insert(String word) {
  11.         Trie node = this;
  12.         for (int i = 0; i < word.length(); i++) {
  13.             int index = word.charAt(i)-'a';
  14.             if (node.children[index] == null) {
  15.                 node.children[index] = new Trie(); //表示该位置有字母，仅由小写字母构成
  16.             }
  17.             node = node.children[index];
  18.         }
  19.         node.isEnd = true;
  20.     }
  21.     public Trie searchPrefix(String prefix) {
  22.         Trie node = this;
  23.         for (int i = 0; i < prefix.length(); i++) {
  24.             int index = prefix.charAt(i) - 'a';
  25.             if (node.children[index] == null) {
  26.                 return null;
  27.             }
  28.             node = node.children[index];
  29.         }
  30.         return node;
  31.     }
  32.     public boolean search(String word) {
  33.         Trie node = searchPrefix(word);
  34.         return node != null && node.isEnd;
  35.     }
  36.     public boolean startWith(String prefix) {
  37.         return searchPrefix(prefix) != null;
  38.     }
  39. }

211. 添加与搜索单词 - 数据结构设计

思路：还是前缀树的思路，但是添加了’.’的处理
``