题解 | #字典树的实现#

#include <string>
#include <vector>
class Trie
{
private:
    const static int MaxN = 1500001;//如果数据变多，就改大这个值
    int tree[MaxN][26] = { {0} };//tree数组
    int pass[MaxN] = {0};//记录走过这个节点的次数
    int end[MaxN]={0};//记录以这个节点结尾的单词次数
    int cnt;//第cnt个位置
public:

    Trie() {
        cnt = 1;
    }
//插入
    void insert(string word) {
        int cur = 1;//每次都要从1开始，也就是根节点开始找
        pass[cur]++;//根节点++
        for (int i = 0; i < word.size(); i++)
        {
            int path = word[i] - 'a';//得到的是整数，例如'z'-'a'=25
            //判断这个节点之前是否存在过
            if (tree[cur][path] == 0)
            {
                //不存在，就++cnt，给予位置
                tree[cur][path] = ++cnt;
            }
            //更新路径节点
            cur=tree[cur][path];
            //更新路径的节点的经过次数
            pass[cur]++;
        }
        //更新以这个字母作为结尾的单词的次数
        end[cur]++;
    }

    int search(string word) {
        int cur = 1;
        for (int i = 0; i < word.size(); i++)
        {
            int path = word[i] - 'a';
            //如果这个字母在路径中的值为0，说明根本不存在包含这个字母的单词
            if (tree[cur][path] == 0)
            {
                return 0;
            }
            cur = tree[cur][path];
        }
        //结束后，要判断输入的单词是不是前缀树已经插入的单词
        //因为有可能插入apple，判断app，app虽然满足前面的条件
        //但是app的最后一个p的end值为0，因为它之前没有被插入。
        if (end[cur] == 0) return 0;
        return 1;
    }

    int startsWith(string prefix) {
        int cur = 1;
        for (int i = 0; i < prefix.size(); i++)
        {
            int path = prefix[i] - 'a';
            if (tree[cur][path] == 0)
            {
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];//返回的是pass数组对应的值
    }

    void deleteTrie(string word)
    {
        if (search(word) > 0)
        {
            int cur = 1;
            for (int i = 0; i < word.size(); i++)
            {
                int path = word[i] - 'a';
                //二维数组的好处就是，如果删除这个节点的路径值
                //那么他后面的关联节点全都断开了
                //因为cnt必定是不一样的。
                if (--pass[tree[cur][path]] == 0)
                {
                    tree[cur][path] = 0;
                }

                cur = tree[cur][path];
            }
            end[cur]--;
        }
    }
//处理脏数据
    void clear()
    {
        for (int i = 1; i <= cnt; i++)
        {
            fill(&tree[i][0], &tree[i][26], 0);
            end[i] = 0;
            pass[i] = 0;
        }
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
     vector<string> res;
     const string ResULTS[2]={"NO","YES"};
     Trie trie;
     for(vector<string> op:operators)
     {
        if(op[0]=="1")
        {
            trie.insert(op[1]);
        }
        else if(op[0]=="2")
        {
            trie.deleteTrie(op[1]);
        }
        else if(op[0]=="3")
        {
            res.push_back(ResULTS[trie.search(op[1])]);
        }
        else if(op[0]=="4")
        {
             res.push_back(to_string(trie.startsWith(op[1])));
        }
     }
     trie.clear();
     return res;
    }
};