数据结构-Trie 字典树

        字典树主要用于存储字符串，查找速度主要字符串元素（单词）的长度有关O(w)。字符串的推荐系统，可以通过字典树来实现，也是一种深度优先搜索单词的方法。利用字符串公共前缀来查询单词，进行搜索引擎推荐。字典树的查询效率非常高，但是大量的数组并没有元素，空间利用率低，是典型的空间换时间。

Trie中节点的定义：

    1. 单词是否结束

    2. 前缀/单词

    3. 记录单词数量

    4. 孩子节点，每个节点都有26个指向下个节点的指针，26个代表有26个字母的可能

/**
 * 字典树!!!======================================================!!!
 */
/**
 * 字典树节点
 */
private static class TrieNode {
    //单词是否结束
    private boolean end;
    //单词
    private String prefix;
    //单词可重复，数量
    private int count;
    //孩子节点
    private TrieNode[] children = new TrieNode[26];
}

/**
 * 字典树
 */
private static class Trie {
    //根节点
    private TrieNode root = new TrieNode();
    /**
     * 插入单词
     *
     * @param products
     */
    private void insertWord(String[] products) {
        for (String p : products) {
            insertWord(p);
        }
    }

    private void insertWord(String product) {
        TrieNode node = root;
        for (char c : product.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        if (!node.end) {
            node.end = true;
            node.prefix = product;
        }
        node.count++;
    }

    /**
     * 查询单词
     *
     * @param searchWord
     * @return
     */
    private List<List<String>> searchWord(String searchWord) {
        List<List<String>> result = new ArrayList<>(searchWord.length());
        for (int i = 0; i < searchWord.length(); i++) {
            result.add(searchPrefix(searchWord.substring(0, i + 1)));
        }
        return result;
    }

    /**
     * 查询单词前缀
     *
     * @param pattern
     * @return
     */
    private List<String> searchPrefix(String pattern) {
        List<String> temp = new ArrayList<>();
        TrieNode node = root;
        for (char c : pattern.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                return temp;
            }
            node = node.children[c - 'a'];
        }
        suggest(node, temp);
        return temp;
    }

    /**
     * 递归深度优先搜索单词
     *
     * @param node
     * @param temp
     */
    private void suggest(TrieNode node, List<String> temp) {
        if (node.end) {
            for (int i = 0; i < node.count; i++) {
                temp.add(node.prefix);
                if (temp.size() == 3) {
                    return;
                }
            }
        }
        for (TrieNode t : node.children) {
            if (t != null) {
                suggest(t, temp);
            }
            //注意这里也需要添加==3的判断，否则会继续递归，导致size>3
            if (temp.size() == 3) {
                return;
            }
        }
    }
}