力扣 6183周赛：字符串的前缀分数和 ——Trie树

通过这道周赛题，来记录一下，Trie树（前缀树），又称字典树，字符查找树

首先Trie树的作用是快速存储和查询字符串集合的一种树

现在只讲模板，进行自己日后复习了

先设全局变量

int tr[N][26];     //26对应26个英文单词，可以看做26叉树

int cnt[N];        //cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）

int idx;             //idx表示当前要插入的节点是第几个,每创建一个节点值+1

 构造插入函数

//传统Trie树是记录最后一个字符为结尾的字符串数量，本题是需要记录每个字符！  
  void insert(string&word)    //插入函数，插入的同时维护trie树结构
    {
        int p=0;                //初始p为0，类似指针，指向当前节点
        for(auto&c:word)        //遍历该单词的字符
        {
            int u=c-'a';        //算出当前字符的下标，即在tr[i][j]中j的下标
            if(!tr[p][u]) tr[p][u]=++idx;   //如果当前trie树没有该下标，则构建
            p=tr[p][u];         //同时更新p，使p指向这个遍历的字符所在节点
            cnt[p]++;           //更新cnt数组，cnt数组是以当前节点结束的字符串数量
        }
    }

构造query函数

    int query(string&word)    //构造查询函数
    {
        int p=0,res=0;        //同样初始化p为0，同时定义一个返回值 res
        for(auto&c:word)      //遍历word
        {    
            int u=c-'a';
            p=tr[p][u];  
            res+=cnt[p];      //把res加上以这个单词的字符为结尾的计数数组cnt
        }
        return res;           //最后res得到的就是这个单词全部的非空前缀总和
    }

题目Trie树解法代码

//使用TRIE树
    const int N=1e6+10;
    int tr[N][26],cnt[N],idx;   //trie树模板
 
class Solution {
public:
    void insert(string&word)
    {
        int p=0;
        for(auto&c:word) 
        {
            int u=c-'a';
            if(!tr[p][u]) tr[p][u]=++idx;
            p=tr[p][u]; 
            cnt[p]++;
        }
    }
    int query(string&word)
    {
        int p=0,res=0;
        for(auto&c:word)
        {
            int u=c-'a';
            p=tr[p][u];
            res+=cnt[p];
        }
        return res;
    }
    vector<int> sumPrefixScores(vector& words) {
        idx=0;
        memset(tr,0,sizeof(tr));
        memset(cnt,0,sizeof cnt);
 
        for(auto&c:words) insert(c);
 
        vector<int>res;
        for(auto&word:words)
        {
            res.push_back(query(word));
        }
        return res;
    }
};

题目字符串哈希解法代码

//可看我之前写得字符串哈希博客，里面有字符串哈希理解
//字符串哈希需要两次遍历，第一次是维护hash表，第二次是将每个单词答案加入答案数组里
typedef unsigned long long ULL;
const int P=13331;
class Solution {
public:
    vector<int> sumPrefixScores(vector& words) {
        unordered_mapint> hash;
        for(auto&word:words)
        {
            ULL x=0;
            for(char c:word)
            {
                x=x*P+c;
                hash[x]++;  //记录当前子字符串
            }
        }
        vector<int> ans;  
        for(auto&s:words)
        {
            ULL x=0;
            int t=0;
            for(auto&c:s)
            {
                x=x*P+c;
                t+=hash[x];
            }
            ans.push_back(t);
        }
        return ans;
    }
};