字典树，也叫前缀树，从名称上就可以看出来，它比较适合用于前缀匹配。字典树的基本结构是一棵多叉树，每 个节点表示一个字符，从根节点到每一个叶子节点都表示一个字符串（事实上，这里不仅仅是叶子节点），准确来 说是结束节点，即每个节点都有一个标识符tag，表示当前节点是否是一个结束节点。另外每个节点都还需要某种 数据结构来保存其子节点，这里的数据结构就是不同的实现方法了，常规一点就是使用数组，当然也可以用链表 或者map。

208、LeetCode上有一些关于字典树的题目，其中第一道就是实现一棵字典树，基本功能包括：

  • 插入字符串到一棵树中
  • 判断字符串是否在给定的一棵树中
  • 判断字符串是否是树中的某个前缀

　　并且这道题目，限制了假设所有的字符都是小写英文字母，也就是说，一共只有26个字符，那么每一个节点的子节点也就最 多包含26个子节点；这里常规的思路就是使用一个数组存储其子节点了，整个字典树的代码如下：

class Trie {

    class TrieNode {
        TrieNode[] children;
        boolean isEnding;
        public TrieNode() {
            children = new TrieNode[26];
            isEnding = false;
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            if (cur.children[array[i] - 'a'] == null) {
                cur.children[array[i] - 'a'] = new TrieNode();
            }
            cur = cur.children[array[i] - 'a'];
        }
        cur.isEnding = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            //不含有当前节点
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        //当前节点是否为是某个单词的结束
        return cur.isEnding;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] array = prefix.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        return true;
    }
}

211、请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配

　　这道题目不再简单的是实现一棵字典树的三大基本功能了，它的查找函数要求不太一样，待查找的单词中可能包含.号，表示可以与任意的字母 相匹配，也就是search函数需要考虑到遍历的字符可能等于.的情况。下面看一下search函数的代码，其他代码和上一道题目是一模一样的。 可以本地debug一遍流程，尤其递归的流程并不容易理解。

    public boolean search(String word) {
        return search(word, root);
    }

    private boolean search(String word, TrieNode root) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            // 对于 . , 递归的判断所有不为空的孩子
            if(array[i] == '.'){
                for(int j = 0;j < 26; j++){
                    if(cur.children[j] != null){
                        if(search(word.substring(i + 1),cur.children[j])){
                            return true;
                        }
                    }
                }
                return false;
            }
            
            //如果当前遍历的字符不等于.，则照常进行；如果等于.，则需要像上面的代码一样，递归的遍历不为空的子节点
            // 不含有当前节点
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        // 当前节点是否为是某个单词的结束
        return cur.isEnding;
    }