字典树，前缀树的模板！秒懂

由于自己还是非常喜欢字典树这个数据结构，每次都觉得很有高级的感觉，在此将自己做练习期间遇到的字典树的模板做一下记录。下面两个基本上是一种模板，都是用到了插入以及搜索的过程中，用到了this指针。this 指针的用法以后自己应该多思考一下，因该如何运用。

class Trie {
private:
    //数组初始化只有全为0才能这样写
    Trie* arc[27]={NULL};
    int val=0;
public:
    /** Initialize your data structure here. */
    Trie(){}

    /** Inserts a word into the trie. */
    void insert(string &word,int start,int _val) {
        Trie* p=this;
        int size=word.size();
        for (int i=start;i<size;++i)
        {
            int index= word.at(i)=='#' ? 26 : word.at(i)-'a';
            if (p->arc[index]==NULL)
                p->arc[index]=new Trie;
            p=p->arc[index];
            p->val=max(p->val,_val);
        }
    }

    int search(string &word) {
        Trie* p=this;
        int size=word.size();
        for (int i=0;i<size;++i)
        {
            int index= word.at(i)=='#' ? 26 : word.at(i)-'a';
            if (p->arc[index]==NULL)
                return -1;
            else
                p=p->arc[index];
        }
        return p->val;
    }
};
class WordFilter {
    Trie trie;
public:
    WordFilter(vector<string>& words) {
        int words_size=words.size();
        string s;
        for (int i=0;i<words_size;++i)
        {
            s=words.at(i)+"#"+words.at(i);
            int words_i_size=words.at(i).size();
            for (int j=0;j<=words_i_size;++j)
                trie.insert(s,j,i);
        }
    }

    int f(string prefix, string suffix) {
        string target=suffix+"#"+prefix;
        return trie.search(target);
    }
};

class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        memset(child,0,sizeof(child));
        //isEnd=false;
        val=0;
        //sum=0;
    }

    void insert(string key, int val) {
        MapSum* ms=this;
        for(auto c:key){
            if(ms->child[c-'a']==NULL){
                ms->child[c-'a']=new MapSum();
            }
            //ms->sum+=val;
            ms = ms->child[c-'a'];
        }
        //ms->isEnd=true;
        ms->val=val;
        //ms->sum=val;
    }

    int sum(string prefix) {
        int ret=0;
        MapSum* ms=this;
        for(auto c:prefix){
            if(ms->child[c-'a']==NULL){
                return 0;
            }
            ms=ms->child[c-'a'];
        }
        ret+=ms->val;
        for(int i=0;i<26;i++){
            if(ms->child[i]==NULL) continue;
            ret+=ms->child[i]->sum("");
        }
        return ret;
    }
private:
    MapSum* child[26];
    //bool isEnd;
    int val;
    //int sum=0;
};

下面这个模板，更加的模块话，可用性更强。 在字典树的每一个节点可以设置一些标志位，例如isend 这样的bool 类型数据，这个数据就是看当然这个节点是不是某一个单词的结尾单词。

//字典树节点
class TrieNode{
private:
    bool isEnd;//单词结束标记
    int index;//单词序号
    vector<TrieNode*> children;//子节点
public:
    //构造
    TrieNode():index(-1),isEnd(false){
        children = vector<TrieNode*>(26, nullptr);
    }
    //析构
    ~TrieNode(){
        for(int i = 0;i < 26;i++)
        {
            if( children[i]) 
            {
                delete children[i];
                children[i] = nullptr;
            }
        }
    }
    //对外接口
    int getIndex() { return index;}
    void setIndex( int i) { index = i;}
    bool isWordEnd() { return isEnd;}
    void SetEnd(){ isEnd = true ;}
    //插入一个字符到子节点
    TrieNode* insertNode(char c) {
        if( !('a' <= c <= 'z') ) return nullptr;
        int id = c-'a'; 
        if( children[id] == nullptr ) {
            children[id] = new TrieNode();   
        }
        return children[id];
    }
    //在子节点中查找一个字符
    TrieNode* getNode(char c){
        if( !('a' <= c <= 'z') ) return nullptr;
        int id = c-'a';
        return children[id];
    }
};

//字典树
class Trie{
private:
    TrieNode * root;//根节点
public:
    Trie():root(new TrieNode()){}
    ~Trie() { delete root;}  
    //插入一个单词及序号
    void insert( string word,int index) {
        TrieNode * p = root;
        for(int i = 0; i < word.size(); i++){
            p = p->insertNode(word[i]);
        }
        p->SetEnd();
        p->setIndex(index);
    }
    //查找一个字符串
    TrieNode* getNode(string word) {
        TrieNode* p = root;
        for(int i = 0; i < word.size(); i++){
            p = p->getNode(word[i]) ;
            if( p == NULL ) return NULL;
        }
        return p;
    }
    //查找一个单词，返回序号
    bool  search(string word,int  &index) {
        TrieNode * p = getNode(word);
        if( p ) {
            index = p->getIndex();
            return  p->isWordEnd();
        }
        return false;
    }    
};