6183. 字符串的前缀分数和(每日一难phase2--day18)

6183. 字符串的前缀分数和

给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。

定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。

例如，如果 words = [“a”, “ab”, “abc”, “cab”] ，那么 “ab” 的分数是 2 ，因为 “ab” 是 “ab” 和 “abc” 的一个前缀。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。

注意：字符串视作它自身的一个前缀。

示例 1：

输入：words = [“abc”,“ab”,“bc”,“b”]
输出：[5,4,3,2]
解释：对应每个字符串的答案如下：

• “abc” 有 3 个前缀：“a”、“ab” 和 “abc” 。
• 2 个字符串的前缀为 “a” ，2 个字符串的前缀为 “ab” ，1 个字符串的前缀为 “abc” 。 总计 answer[0] = 2 + 2 + 1 = 5 。
• “ab” 有 2 个前缀：“a” 和 “ab” 。
• 2 个字符串的前缀为 “a” ，2 个字符串的前缀为 “ab” 。 总计 answer[1] = 2 + 2 = 4 。
• “bc” 有 2 个前缀：“b” 和 “bc” 。
• 2 个字符串的前缀为 “b” ，1 个字符串的前缀为 “bc” 。 总计 answer[2] = 2 + 1 = 3 。
• “b” 有 1 个前缀：“b”。
• 2 个字符串的前缀为 “b” 。 总计 answer[3] = 2 。

示例 2：

输入：words = [“abcd”]
输出：[4]
解释： “abcd” 有 4 个前缀 “a”、“ab”、“abc” 和 “abcd”。每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 1000 words[i]
由小写英文字母组成

解析：

可以使用字典树，做法如下：

• 将所有字符串加入字典树，每个节点还需要维护一个分数，代表有多少字符串经过该结点（也就是该字符串可以做多少字符串的前缀）；
• 同时，该节点还需要在字符串的末尾标记该字符串的id；
• 然后dfs字典树中所有路径
  
  代码参考

代码：

class Solution {
    struct Node{
        Node* son[26]{};
        vector<int> ids;
        int scores;
    };
public:

    // 遍历每一个节点
    vector<int> ans;
    void dfs(Node* root,int sum){
        if(!root)   
            return;
        // sum记录一条路径上各节点总和
        sum+=root->scores;
        // 如果该节点为一个字符串的最后一个结点，就给该点赋值
        for(auto a :root->ids){
            ans[a]+=sum;
        }
        for(auto a:root->son){
            dfs(a,sum);
        }
    }

    vector<int> sumPrefixScores(vector<string>& s) {
        int n=s.size();

        // 字典树根节点
        Node* root=new Node();
        for(int i=0;i<n;i++){
            Node* cur=root;
            // 将字符串插入字典树
            for(char c:s[i]){
                c-='a';
                if(cur->son[c]==nullptr)
                    cur->son[c]=new Node();
                cur=cur->son[c];
                ++cur->scores;
            }
            // 在字符串末尾处放入以该节点为结尾的字符串下标
            cur->ids.push_back(i);
        }
        ans.resize(n);
        // 遍历字符串上的每一条路径
        dfs(root,0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48