题解 | #字典树的实现#

字典树的实现

http://www.nowcoder.com/practice/a55a584bc0ca4a83a272680174be113b

解法一：哈希表实现（暴力解法）

题目要求实现字符串的「插入」、「查找」、「查找前缀」等功能，一个直观的想法是利用「以空间换时间」的数据结构：哈希表。哈希表在「查找」操作上的时间复杂度为 $O(1)$ ，可以作为此题的解法。

利用哈希表实现的思路如下：

定义哈希表hash，其保存的键值对为 $<string, int>$ ，即以「单词」作为key，以「该单词出现的次数」作为value。
对于插入操作：首先判断该单词是否存在在哈希表中，若存在，将其value加1；若不存在，将其插入哈希表中，并将value置为1。
对于删除操作：由于被删除的单词一定存在于哈希表中（题目明确说明），故直接将该单词的value减1即可。
对于查找操作：直接在哈希表中查找该单词，若该单词存在在哈希表的key中、且value大于0，说明查找成功，否则查找失败。
对于查找前缀操作：查找前缀利用到c++的库函数 $find(string\quad subStr)$ ，该函数在字符串中查找 $subStr$ 字符串，若找到，返回其起始下标。因此可以通过判断该函数的返回值是否为0（即从第一个位置开始）来判断是否存在前缀。

基于上述思路，实现的代码如下：（注意：此方法超出时间限制）

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函数查找前缀
                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; 
    }
};

时间复杂度：对于插入操作，哈希表首先查找该单词是否存在（时间复杂度为 $O(1)$ ），随后改变其value（时间复杂度为 $O(1)$ ）；对于查找操作，哈希表查找的时间复杂度为 $O(1)$ ；对于删除操作，仅是将该单词的value减1，故时间复杂度为 $O(1)$ ；对于查找前缀操作，需要遍历前缀，设前缀的长度为 $L$ ，则时间复杂度为 $O(L)$ 。

空间复杂度：哈希表为每个单词维护一个键值对，故空间复杂度为 $O(L)$ ，其中 $L$ 为单词长度。

解法二：TrieNode实现

解法一利用哈希表需要「为每个单词单独维护一个 $<string, int>$ 键值对」，较为复杂。此题还可以通过定义 $TrieNode$ 树实现。该树的每个结点包含：一个长度为26的数组 $next$ （数组的每一个元素为指向 $TrieNode$ 类型的指针）、一个int类型变量 $cnt$ （统计当前字母被访问了多少次，为方便实现删除操作和查找前缀操作）、一个bool类型变量 $isEnd$ （用来表示当前结点是否是某一个单词的结尾），如下所示。

struct TrieNode {
    bool isEnd; // 用来表示当前结点是否是单词末尾
    int cnt; // 统计当前字母被访问了多少次
    TrieNode* next[26]; 
    TrieNode() {
        cnt = 0; // 初始化为0
        isEnd = false; // 初始化为false
        for (int i = 0; i < 26; i ++) {
            next[i] = NULL; // 初始化为NULL
        }
    }
};

注意：在树的每个结点中，并不「实际储存某个字母」，而是记录「该字母所对应的索引」，具体如下图所示。

下图展示「插入」和「查找」的过程：

图片说明

对于插入操作：
1. 若待插入的字母已经存在在某个结点中了，则将其 $cnt$ 变量加1，表示「多一次访问」；
2. 反之，则为「该字母所对应的数组元素（也就是 $next$ 指针）」 $new$ 一个空间，即：该位置的指针不再为 $NULL$ 。
3. 在插入到「最后一个字母」时，将该结点的 $isEnd$ 标志置位 $true$ ，代表这是最后一个字符。
对于删除操作：
1. 由于所删除的字母一定事先存在于树中，故可以简单地通过改变 $cnt$ 变量的取值来实现：即将 $cnt$ 变量减1，代表「访问该结点的次数减少一次」；
2. 若某个结点的 $cnt$ 变量为0，代表该字母全部删除。
对于查找操作：
1. 查找过程即遍历整个树，若「结点指针为空」或「结点的 $cnt$ 变量为0」，则说明该字母不存在，直接返回 $false$ ；
2. 遍历完整个单词后到达最后一个结点，若该结点的 $isEnd$ 变量为 $true$ ，说明「是某一个单词的结尾」，此时返回 $true$ ，否则返回 $false$ 。
对于查找前缀操作：
1. 查找前缀过程即遍历整个树，若「结点指针为空」或「结点的 $cnt$ 变量为0」，则说明该字母不存在，直接返回 $false$ ；
2. 在遍历过程中，记录所有结点的 $cnt$ 变量的最小值，即为「共同前缀」。

根据上述代码，实现的思路如下：

struct TrieNode {
    bool isEnd; // 用来表示当前结点是否是单词末尾
    int cnt; // 统计当前字母被访问了多少次
    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]) // 结点指针为空
                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; 
    }
};

时间复杂度：在插入、删除、查找等操作时需要遍历整个单词，故时间复杂度为 $O(L)$ ，其中 $L$ 为单词长度；

空间复杂度：设树的结点个数为 $N$ ，组成所有单词的字母个数为 $K$ （此题为26个字母），则每个树结点需要 $O(K)$ 的空间，因此整个空间复杂度为 $O(N*K)$ 。