又学到一种结构：前缀树！

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

  正好今天力扣每日一题遇上了，查缺补漏，安排上！
  个人对前缀树的理解就是：不多写一个字母！！！比如你要存储word和world，那么最终集合里面在r的后面就开始分叉，一条路指向d，另一条路指向ld；

实现分析
假如我们存储的是小写字母组成的字符串，如力扣208，那么首先我们可以定义一个节点Trie，然后他有26个子指针（因为下一个字符的可能性有26种嘛！）；还需要有一个标志位，指示当前节点是否是字符结束的位置（假如你存储world，那么你查询wor的时候，如果没有一个判断结束的标志位，那么你就会得到错误的结果（wor存在，实际上不存在））

class Trie {
   
private:
    vector<Trie*> children;
    bool isEnd;
public:
    /** Initialize your data structure here. */
    //前缀树，字典树，也就是共用前缀的一种结构
    //对于每一个节点，都有指向26个小写字母的可能，所以每一个节点有children数组。存储26个Trie类型的指针，然后还有一个标识位，标记当前节点是否是字符串的末尾
    Trie():children(26),isEnd(false){
   }//构造函数
    
    /** Inserts a word into the trie. */
    void insert(string word) {
   
        //插入操作：遍历每一个字符，看当前字符是否来自上一个字符的一个子指针
        Trie* node=this;//this指向当前这个类本身的地址
        for(auto c:word){
   
            int index=c-'a';
            if(node->children[index]==nullptr){
   //如果当前字符不是来自上一个字符的子指针
                node->children[index]=new Trie();//那么我就创建它
            }
            node=node->children[index];
        }
        node->isEnd=true;//标记当前节点为end
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
   
        //查找一棵树是否存在前缀树里面
        Trie* node=this;
        for(auto c:word){
   
            int index=c-'a';
            if(node->children[index]==nullptr){
   
                return false;
            }
            node=node->children[index];
        }
        return node->isEnd;//如果当前节点标记为end，就是存在word
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
   
        Trie* node=this;
        for(auto c:prefix){
   
            int index=c-'a';
            if(node->children[index]==nullptr){
   
                return false;
            }
            node=node->children[index];
        }
        return true;
    }
};

/** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */