解法一：哈希表實現(xiàn)（暴力解法）

題目要求實現(xiàn)字符串的「插入」、「查找」、「查找前綴」等功能，一個直觀的想法是利用「以空間換時間」的數(shù)據(jù)結(jié)構(gòu)：哈希表。哈希表在「查找」操作上的時間復(fù)雜度為，可以作為此題的解法。

利用哈希表實現(xiàn)的思路如下：

1. 定義哈希表hash，其保存的鍵值對為，即以「單詞」作為key，以「該單詞出現(xiàn)的次數(shù)」作為value。

2. 對于插入操作：首先判斷該單詞是否存在在哈希表中，若存在，將其value加1；若不存在，將其插入哈希表中，并將value置為1。

3. 對于刪除操作：由于被刪除的單詞一定存在于哈希表中（題目明確說明），故直接將該單詞的value減1即可。

4. 對于查找操作：直接在哈希表中查找該單詞，若該單詞存在在哈希表的key中、且value大于0，說明查找成功，否則查找失敗。

5. 對于查找前綴操作：查找前綴利用到c++的庫函數(shù)，該函數(shù)在字符串中查找字符串，若找到，返回其起始下標(biāo)。因此可以通過判斷該函數(shù)的返回值是否為0（即從第一個位置開始）來判斷是否存在前綴。

基于上述思路，實現(xiàn)的代碼如下：（注意：此方法超出時間限制）

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    unordered_map <string, int> hash; // 定義哈希表
    void insert(string word) {
        if (hash.find(word) != hash.end()) // 單詞存在在哈希表中
            hash[word] += 1; 
        else // 單詞不存在在哈希表中
            hash[word] = 1; 
        return; 
    }
    void remove(string word) {
        hash[word]--; // 直接將該單詞的value減1
        return; 
    }
    bool search(string word) {
        if (hash.find(word) != hash.end()) // 單詞存在在哈希表中
            return hash[word] != 0; // 若該單詞的value不為0，說明存在
        return false; 
    }
    int searchPrefix(string word) {
        int res = 0; 
        for (auto it = hash.begin(); it != hash.end(); it++) { // 遍歷哈希表
            string hashKey = it->first; 
            if (hashKey.find(word) == 0) // 利用find函數(shù)查找前綴
                res += it->second; 
        }
        return res; 
    }
    vector<string> trieU(vector<vector<string> >& operators) {
        vector<string> res; 
        for (int i = 0; i < operators.size(); i++) {
            string op = operators[i][0], word = operators[i][1]; 
            if (op == "1") { // 插入
                insert(word); 
            } else if (op == "2") { // 刪除
                remove(word); 
            } else if (op == "3") { // 查找
                int searchRes = search(word); 
                if (searchRes) 
                    res.push_back("YES"); 
                else 
                    res.push_back("NO"); 
            } else if (op == "4") { // 查找前綴
                int searchPrefixRes = searchPrefix(word); 
                res.push_back(to_string(searchPrefixRes)); 
            }
        }
        return res; 
    }
};

時間復(fù)雜度：對于插入操作，哈希表首先查找該單詞是否存在（時間復(fù)雜度為），隨后改變其value（時間復(fù)雜度為）； 對于查找操作，哈希表查找的時間復(fù)雜度為；對于刪除操作，僅是將該單詞的value減1，故時間復(fù)雜度為；對于查找前綴操作，需要遍歷前綴，設(shè)前綴的長度為，則時間復(fù)雜度為。

空間復(fù)雜度：哈希表為每個單詞維護一個鍵值對，故空間復(fù)雜度為，其中為單詞長度。

解法二：TrieNode實現(xiàn)

解法一利用哈希表需要「為每個單詞單獨維護一個鍵值對」，較為復(fù)雜。此題還可以通過定義?樹實現(xiàn)。該樹的每個結(jié)點包含：一個長度為26的數(shù)組（數(shù)組的每一個元素為指向類型的指針）、一個int類型變量（統(tǒng)計當(dāng)前字母被訪問了多少次，為方便實現(xiàn)刪除操作和查找前綴操作）、一個bool類型變量（用來表示當(dāng)前結(jié)點是否是某一個單詞的結(jié)尾），如下所示。

struct TrieNode {
    bool isEnd; // 用來表示當(dāng)前結(jié)點是否是單詞末尾
    int cnt; // 統(tǒng)計當(dāng)前字母被訪問了多少次
    TrieNode* next[26]; 
    TrieNode() {
        cnt = 0; // 初始化為0
        isEnd = false; // 初始化為false
        for (int i = 0; i < 26; i ++) {
            next[i] = NULL; // 初始化為NULL
        }
    }
}; 

注意：在樹的每個結(jié)點中，并不「實際儲存某個字母」，而是記錄「該字母所對應(yīng)的索引」，具體如下圖所示。

下圖展示「插入」和「查找」的過程：

1. 對于插入操作：

   1. 若待插入的字母已經(jīng)存在在某個結(jié)點中了，則將其變量加1，表示「多一次訪問」；
   2. 反之，則為「該字母所對應(yīng)的數(shù)組元素（也就是指針）」一個空間，即：該位置的指針不再為。
   3. 在插入到「最后一個字母」時，將該結(jié)點的標(biāo)志置位，代表這是最后一個字符。

2. 對于刪除操作：

   1. 由于所刪除的字母一定事先存在于樹中，故可以簡單地通過改變變量的取值來實現(xiàn)：即將變量減1，代表「訪問該結(jié)點的次數(shù)減少一次」；
   2. 若某個結(jié)點的變量為0，代表該字母全部刪除。

3. 對于查找操作：

   1. 查找過程即遍歷整個樹，若「結(jié)點指針為空」或「結(jié)點的變量為0」，則說明該字母不存在，直接返回；
   2. 遍歷完整個單詞后到達最后一個結(jié)點，若該結(jié)點的變量為，說明「是某一個單詞的結(jié)尾」，此時返回，否則返回。

4. 對于查找前綴操作：

   1. 查找前綴過程即遍歷整個樹，若「結(jié)點指針為空」或「結(jié)點的變量為0」，則說明該字母不存在，直接返回；
   2. 在遍歷過程中，記錄所有結(jié)點的變量的最小值，即為「共同前綴」。

?

根據(jù)上述代碼，實現(xiàn)的思路如下：

struct TrieNode {
    bool isEnd; // 用來表示當(dāng)前結(jié)點是否是單詞末尾
    int cnt; // 統(tǒng)計當(dāng)前字母被訪問了多少次
    TrieNode* next[26]; 
    TrieNode() {
        cnt = 0; // 初始化為0
        isEnd = false; // 初始化為false
        for (int i = 0; i < 26; i ++) {
            next[i] = NULL; // 初始化為NULL
        }
    }
}; 

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

    TrieNode* root = new TrieNode(); 
    void insert(string str) {
        TrieNode *p = root; 
        for (int i = 0; i < str.size(); i ++) {
            int idx = str[i] - 'a'; 
            if (!p->next[idx]) // 結(jié)點指針為空
                p->next[idx] = new TrieNode();
            p->next[idx]->cnt ++; // cnt變量加1
            p = p->next[idx]; // 向下移動
        }
        p->isEnd = true; // 單詞的末尾
    }

    bool search(string str) {
        TrieNode *p = root; 
        for (int i = 0; i < str.size(); i ++) {
            int idx = str[i] - 'a'; 
            if (!p->next[idx] || !p->next[idx]->cnt) // 若指針為空，或者cnt為0
                return false; 
            p = p->next[idx]; // 向下移動
        }
        return p->isEnd; // 是否為某個單詞的末尾字母
    }

    int searchPrefix(string str) {
        TrieNode *p = root; 
        int res = INT_MAX; 
        for (int i = 0; i < str.size(); i ++) {
            int idx = str[i] - 'a'; 
            if (!p->next[idx] || !p->next[idx]->cnt) // 指針為空，或cnt為0
                return 0; 
            res = min(res, p->next[idx]->cnt); // 記錄cnt最小值
            p = p->next[idx]; 
        }
        return res; 
    }

    void remove(string str) {
        TrieNode *p = root; 
        for (int i = 0; i < str.size(); i ++) {
            int idx = str[i] - 'a'; 
            p->next[idx]->cnt --; // cnt變量減1
            p = p->next[idx]; 
        }
    }

    vector<string> trieU(vector<vector<string> >& operators) {
        vector<string> res; 
        for (int i = 0; i < operators.size(); i ++) {
            string op = operators[i][0], str = operators[i][1]; 
            if (op == "1") {
                // 插入
                insert(str); 
            } else if (op == "2") {
                // 刪除
                remove(str); 
            } else if (op == "3") {
                // 查找
                bool searchRes = search(str); 
                if (searchRes) 
                    res.push_back("YES"); 
                else 
                    res.push_back("NO"); 
            } else if (op == "4") {
                // 查找前綴
                int prefixNum = searchPrefix(str); 
                res.push_back(to_string(prefixNum)); 
            }
        }
        return res; 
    }
};

時間復(fù)雜度：在插入、刪除、查找等操作時需要遍歷整個單詞，故時間復(fù)雜度為，其中為單詞長度；

空間復(fù)雜度：設(shè)樹的結(jié)點個數(shù)為，組成所有單詞的字母個數(shù)為（此題為26個字母），則每個樹結(jié)點需要的空間，因此整個空間復(fù)雜度為。