字典树（前缀树Trie）

基本结构

字典树，即Trie树，又称单词查找树或者键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：最大限度的减少无谓的字符串比较，查询效率比哈希表高。

基本性质

节点本身不存完整单词
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点路径代表的字符都不相同。

核心思想

Trie树的核心思想是空间换时间。利用字符串的公告前缀来降低查询时间的开销以达到提高效率的目的。

实现Trie树——leetcode 208

package com.xzt.solutions;

public class Solution208 {
    class Trie {

        private TrieNode root;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char cur = word.charAt(i);
                if (!node.containsKey(cur)) {
                    node.put(cur, new TrieNode());
                }
                node = node.get(cur);
            }
            node.setEnd();
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode node = searchPrefix(word);
            return node != null && node.isEnd();
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private TrieNode searchPrefix(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char cur = word.charAt(i);
                if (!node.containsKey(cur)) {
                    return null;
                }
                node = node.get(cur);
            }
            return node;
        }
    }

    class TrieNode {
        private TrieNode[] links;
        public final int R = 26;
        private boolean isEnd;

        public TrieNode() {
            links = new TrieNode[R];
        }

        public boolean containsKey(char ch) {
            return links[ch - 'a'] != null;
        }

        public TrieNode get(char ch) {
            return links[ch - 'a'];
        }

        public void put(char ch, TrieNode node) {
            links[ch - 'a'] = node;
        }

        public void setEnd() {
            isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }
    }
}