Sum of Prefix Scores of Strings

You are given an array words of sizeco $n$ sisting of non-empty strings.

We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i] .

For example, if words = ["a", "ab", "abc", "cab"] ,then the score of "ab" is $2$, since "ab" is a prefix of both "ab" and "abc" .

Return an array answer of size $n$ where answer[i] is the sum of scores of every non-empty prefix of words[i] .

Note that a string is considered as a prefix of itself.

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

Constraints:

$1 \leq words.length \leq 1000$
$1 \leq words[i].length \leq 1000$
words[i] consists of lowercase English letters.

解题思路

　　这题很容易想到的暴力解法就是枚举每一个字符串$s$，然后枚举出$s$的所有前缀，对于每个前缀再与所有的字符串进行匹配检查是否为某个字符串的前缀，时间复杂度为$O(n^3)$。这个时候就要想到能否把每个前缀与所有的字符串匹配这一步进行优化，即能否通过预处理把这一步的时间复杂度降到$O(1)$。本质上这一步是枚举出所有前缀包含当前前缀子串的字符串个数，因此可以预处理出所有字符串的所有前缀，并统计某个前缀串是多少个字符串的前缀，然后枚举的时候直接查哈希表就可以了。如果哈希表(unordered_map)的键是string的话，其实这一步还是$O(n)$的复杂度，因此还需要把string映射成一个整数，这就可以用到字符串哈希的方法了。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     unsigned long long P = 131;
 4     
 5     vector<int> sumPrefixScores(vector<string>& words) {
 6         unordered_map<unsigned long long, int> mp;
 7         for (auto &s : words) {
 8             unsigned long long t = 0;
 9             for (int i = 0; i < s.size(); i++) {
10                 t = t * P + s[i];
11                 mp[t]++;
12             }
13         }
14         vector<int> ans(words.size());
15         for (int i = 0; i < words.size(); i++) {
16             unsigned long long t = 0;
17             for (int j = 0; j < words[i].size(); j++) {
18                 t = t * P + words[i][j];
19                 ans[i] += mp[t];
20             }
21         }
22         return ans;
23     }
24 };

　　像这类问题还有一种做法是用Trie，如果遇到前缀问题可以想一下Trie能不能做。在插入的过程中每个结点都要加$1$，表示这个前缀是当前字符串的。查询的时候就可以根据前缀累加个数。

　　AC代码如下：

 1 const int N = 1e6 + 10;
 2 
 3 int tr[N][26], cnt[N], idx;
 4 
 5 class Solution {
 6 public:
 7     void insert(string &s) {
 8         int p = 0;
 9         for (auto &c : s) {
10             int t = c - 'a';
11             if (!tr[p][t]) tr[p][t] = ++idx;
12             p = tr[p][t];
13             cnt[p]++;
14         }
15     }
16     
17     int query(string &s) {
18         int p = 0, ret = 0;
19         for (auto &c : s) {
20             int t = c - 'a';
21             p = tr[p][t];
22             ret += cnt[p];
23         }
24         return ret;
25     }
26     
27     vector<int> sumPrefixScores(vector<string>& words) {
28         idx = 0;
29         memset(tr, 0, sizeof(tr));
30         memset(cnt, 0, sizeof(cnt));
31         for (auto &s : words) {
32             insert(s);
33         }
34         vector<int> ans;
35         for (auto &s : words) {
36             ans.push_back(query(s));
37         }
38         return ans;
39     }
40 };

参考资料

　　力扣第311场周赛：https://www.bilibili.com/video/BV1jG4y1B77r