题解 | #字典树的实现#

struct TrieNode {
    int cnt;
    bool end;
    TrieNode* next[26] = {nullptr};
    TrieNode() {
        cnt = 1;
        end = false;
        for (int i = 0; i < 26; i++) next[i] = nullptr;
    }
};
class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    TrieNode* phead = new TrieNode();
    void insert(string word) {
        TrieNode* p = phead;
        for (char ch : word) {
            if (p->next[ch - 'a'] == nullptr) {
                p->next[ch - 'a'] = new TrieNode();
            } else {
                p->next[ch - 'a']->cnt++;
            }
            p = p->next[ch - 'a'];
        }
        p->end = true;
    }

    int prefixNumber(string pre) {
        int ans = INT_MAX;
        TrieNode* p = phead;
        for (char ch : pre) {
            if (p->next[ch - 'a'] == nullptr) return 0;
            ans = min(ans, p->next[ch - 'a']->cnt);
            p = p->next[ch - 'a'];
        }
        return ans;
    }

    void Delete(string word) {
        TrieNode* p = phead;
        for (char ch : word) {
            if (p->next[ch - 'a']->cnt == 1) {
                p->next[ch - 'a'] = nullptr;
                return;
            } else {
                p->next[ch - 'a']->cnt--;
                p = p->next[ch - 'a'];
            }
        }
    }

    bool search(string word) {
        TrieNode* p = phead;
        for (char ch : word) {
            if (p->next[ch - 'a'] == nullptr) return false;
            p = p->next[ch - 'a'];
        }
        return p->end;
    }
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        vector<string> ans;
        for (auto op : operators) {
            string num = op[0], word = op[1];
            if (num == "1") insert(word);
            else if (num == "2") Delete(word);
            else if (num == "3") {
                if (search(word)) {
                    ans.push_back("YES");
                } else {
                    ans.push_back("NO");
                }
            }
            else if (num == "4") {
                int cnt = prefixNumber(word);
                ans.push_back(to_string(cnt));
            }
        }
        return ans;
    }
};