力扣开始教面试题了（bushi

前缀树

 又叫字典树，单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

前缀树的性质：

它有3个基本性质：
 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。

前缀树
 既然是单词查找树，那树中存储的内容大概是只有字母了，那么复杂度最低的方法就是使用一个Trie[26] children来存储数据，并用一个bool isEnd来表示这个节点能不能作为结束节点。
&emsp;当然我看到力扣上这一题的第一反应是用一个Dictionary<char,Trie> dic来存储这个节点的所有子节点，并使用（0,null）这个键值对作为结束节点的标记，但是这样做比数组还慢（
&emsp;先是自己用字典实现的前缀树（看起来还是挺简单的）：

public class Trie {
    //用一个字典存储这个节点的所有直接子节点
    Dictionary<char,Trie> dic;

    //构造函数，用于初始化前缀树
    public Trie() {
        dic = new Dictionary<char,Trie>();
    }
    
    //向前缀树中插入一个单词
    public void Insert(string word) {
        if(word.Length==0){
            //结束标记
            if(!dic.ContainsKey('0'))
                dic.Add('0',null);
            return;
        } 
        if(!dic.ContainsKey(word[0])){
            dic.Add(word[0],new Trie());
        }
        //递归，彳亍！
        dic[word[0]].Insert(word.Substring(1));
    }
    
    //查找某个单词是否在树中，要注意能否找到结束标记
    public bool Search(string word) {
        if(word.Length==0){
            if(dic.ContainsKey('0')) return true;
            else return false;
        } 
        else{
            if(!dic.ContainsKey(word[0])) return false;
            else return dic[word[0]].Search(word.Substring(1));
        }
    }
    
    //查找树中是否有某个前缀，无需考虑是否有结束标记
    public bool StartsWith(string prefix) {
        if(prefix.Length==0) return true;
        if(!dic.ContainsKey(prefix[0])) return false;
        else return dic[prefix[0]].StartsWith(prefix.Substring(1));
    }
}

&emsp;官方提供的使用数组的版本：（java）

class Trie {
    //children[0]代表'a',children[1]代表'b'……
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            //不用分割字符串还是快一些
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}