Leetcode---208.实现Trie前缀树

Java非递归版

class Trie {
    private class Node{
        boolean isTrie;
        Map<Character, Node> children = new HashMap<>();
    }
    
    private Node root = new Node();
    /** Initialize your data structure here. */
    public Trie() {
        
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node node = root;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            if(!node.children.containsKey(c)){
                node.children.put(c, new Node());
            }
            node = node.children.get(c);
        }
        node.isTrie = true;
        return;
        
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node node = root;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            Node temp = node.children.get(c);
            if(temp == null)
                return false;
            node  = temp;
        }
        return node.isTrie;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node node = root;
        for(int i=0; i<prefix.length(); i++){
            char c = prefix.charAt(i);
            Node temp = node.children.get(c);
            if(temp == null)
                return false;
            node  = temp;
        }
        return node!=null;
    }
}

关于Trie

核心思想：空间换取时间
Trie 树又叫又叫字典树、前缀树、单词查找树，它是一颗多叉查找树。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。
如果海量数据是字符串数据，那么就可以用很小的空间开销构建一颗 Trie 树，空间开销和树高有关。

{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”}
基本性质：
- 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符互不相同。
优点
- 插入和查询效率很高，都是O(m)，m是待插入/查询字符串长度；（关于查询，会有人认为hash表时间复杂度O(1)不是更快？确实，但是哈希搜索的效率通常取决于hash函数的好坏，因为这决定着冲突的概率）。
- Trie树中不同关键字不会冲突；
- 可以对关键字按字典排序。
缺点
- 当hash函数很好时，Trie树的查找效率会低于哈希查找；
- 空间消耗比较大。
主要应用：字符串检索、词频统计、字符串排序、前缀匹配等