题解 | #字典树的实现#

1. 牢牢抓住一个节点的孩子才是这个单词，以及搜索的时候记住is_end的计数。。
2. 注意同一个元素不能delete两次。
3. 时时注意插入的时候前缀的定义（自己就是一个前缀）
4. 注意：所有是不是找到和前缀数目，全部由后一个节点确定。
5. 删除注意用栈保存当前元素以及索引。

# define TRIE_MAX_CHAR_NUM 26
class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */

    struct Trienode{
        Trienode* child[TRIE_MAX_CHAR_NUM];
        int is_end;
        int count_;// 相同单词的数目

        Trienode(int count = 0):is_end(0), count_(count){
            for(int i = 0; i < TRIE_MAX_CHAR_NUM;i++){
                child[i] = 0;
            }
        }
    };


    class TrieTree{
    public:
        TrieTree(){

        }

//         ~TrieTree(){
//             for (int i = 0; i< _node_vec.size();i++){
//                 delete _node_vec[i];
//             }
//         }


        void insert(const char* word){
            Trienode* ptr = &_root;

            while(*word){
                int pos = *word - 'a';
                if(!ptr->child[pos]){
                    ptr->child[pos] = new_node();
                    ptr->child[pos]->count_++;
                }else{
                    ptr->child[pos]->count_++;
                }

                ptr = ptr->child[pos];

                word++;

            }
            ptr->is_end++;

        }
        void delete_node(const char* word){

            if(!search(word)){//如果找不到找个单词，那么就把其删除
                return;
            }

            //删的话的倒着删，因此需要栈来保存
            stack<Trienode* >delete_to;
            stack<int> index_node;

            Trienode* ptr = &_root;

            while(*word){
                int pos = *word - 'a';
                if(ptr->child[pos]){
                   ptr->child[pos]->count_--;
                   if(ptr->child[pos]->count_ == 0){
                       delete_to.push(ptr);
                       index_node.push(pos);
                   }
                }

                ptr = ptr->child[pos];
                word++;
            }

            ptr->is_end--;

            //删除
            while(!delete_to.empty()){
                Trienode* node = delete_to.top();delete_to.pop();
                int index = index_node.top();index_node.pop();

                delete node->child[index];
                node->child[index] = NULL;  
            }

        }

        bool search(const char* word){

            if(!word){
                return false;
            }

            Trienode* ptr = &_root;

            while(*word){
                int pos = *word - 'a';
                if(!ptr->child[pos]){
                    return false;
                }

                ptr = ptr->child[pos];
                word++;
            }

            return ptr->is_end>0;


        }

        int prefixNumber(const char* pre){
            Trienode* ptr = &_root;
            if(!pre){
                return 0;
            }
            while(*pre){
                int pos = *pre - 'a';
                if(!ptr->child[pos]){
                    return 0;
                }

                ptr = ptr->child[pos];
                pre++;
            }

            return ptr->count_;

        }

        Trienode* root(){
            return &_root;
        }



    private:
        Trienode* new_node(){
            Trienode* node = new Trienode();
            _node_vec.push_back(node);
            return node;
        }
        vector<Trienode*> _node_vec;
        Trienode _root;
    };



    vector<string> trieU(vector<vector<string> >& operators) {

        vector<string> res;
        TrieTree trie_tree;

        const static string RESULT[] = {"NO","YES"};

        if(!operators.size()){
            return res;
        }

        // write code here
        for(int i = 0; i< operators.size();i++){
            int op = atoi(operators[i][0].c_str());
            const char* str = operators[i][1].c_str();
            switch(op){
                case 1:
                    trie_tree.insert(str);
                    break;
                case 2:
                    trie_tree.delete_node(str);
                    break;
                case 3:
                     res.push_back(RESULT[trie_tree.search(str)]);
                     break;
                case 4:
                     res.push_back(to_string(trie_tree.prefixNumber(str)));
                     break;
             }
        }

        return res;
    }


};