题解 | #字典树的实现#

字典树模板
（1）首先定义节点：
cnt: 当前字母在前缀出现的次数
isWord: 当前字母作为word结尾的次数
next[26]: 字母范围

struct Node{
        int cnt;
        int isWord;
        Node* next[26];
        Node(int _cnt=0){
            cnt = _cnt;
            isWord = 0;
            for(int i = 0; i < 26; i ++) next[i] = NULL;
        }
    };

（2）插入：看代码
（3）删除：这里需要考虑内存泄漏问题，先保存整个路径下的所有cnt为0的节点，说明这些节点需要回收，
其次不能顺序从上到下delete，因为这里用的是指针，还有就是delete后记得置NULL；
（4）查找单词和前缀：看代码；

class Trie{
private:
    struct Node{
        int cnt;
        int isWord;
        Node* next[26];
        Node(int _cnt=0){
            cnt = _cnt;
            isWord = 0;
            for(int i = 0; i < 26; i ++) next[i] = NULL;
        }
    };
    Node* root = new Node(0);
    int num = 1;
public:
    void insertWord(string word){
        Node* p = root;
        for(char ch:word){
            int idx = ch - 'a';
            if(p -> next[idx] == NULL) p -> next[idx] = new Node();
            p = p -> next[idx]; 
            p -> cnt ++;
        }
        p -> isWord ++;
    }
    void deleteWord(string word){
        if(!searchWord(word)) return; 
        //find the nodes that will be deleted;
        Node* p = root;
        Node* pre = root;
        stack<Node*> preStk;
        stack<int> nxtStk;
        int nxtIdx = -1;
        for(char ch:word){
            int idx = ch - 'a';
            pre = p;
            p = p -> next[idx];
            p -> cnt --;
            if(p -> cnt == 0) nxtIdx = idx;
            if(nxtIdx != -1){
                preStk.push(pre);
                nxtStk.push(nxtIdx);
            }
        }
        p -> isWord --;

        //delete node
        while(!preStk.empty()){
            Node* node = preStk.top(); preStk.pop();
            int nxtIdx = nxtStk.top(); nxtStk.pop();
            delete node -> next[nxtIdx];
            node -> next[nxtIdx] = NULL;
        }
    }
    bool searchWord(string word){
        if(word == "") return false;
        Node* p = root;
        for(char ch:word){
            int idx = ch - 'a';
            if(p -> next[idx] == NULL) return false;
            p = p -> next[idx];
        }
        return p -> isWord > 0;
    }
    int getPrefixWordCount(string word){
        if(word == "") return 0;
        Node* p = root;
        for(char ch:word){
            int idx = ch - 'a';
            if(p -> next[idx] == NULL) return 0;
            p = p -> next[idx];
        }
        return p -> cnt;
    }
};
class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        vector<string> res;
        const string RESULTS[2] = {"NO", "YES"};
        Trie trie;
        for(vector<string> op:operators){
            if(op[0] == "1"){
                trie.insertWord(op[1]);
            }else if(op[0] == "2"){
                trie.deleteWord(op[1]);
            }else if(op[0] == "3"){
                res.push_back(RESULTS[trie.searchWord(op[1])]);
            }else if(op[0] == "4"){
                res.push_back(to_string(trie.getPrefixWordCount(op[1])));
            }
        }
        return res;
    }
};