题目链接

Leetcode.2416 字符串的前缀分数和 Rating ： 1725

题目描述

给你一个长度为 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<=10001 <= words.length <= 10001<=words.length<=1000
• 1<=words[i].length<=10001 <= words[i].length <= 10001<=words[i].length<=1000
• words[i]由小写英文字母组成

分析：字典树

对于样例1的 words = ["abc","ab","bc","b"]，我们可以把它们全部插入到一棵 字典树 中。如下图：

我们发现 abc的 前缀分数和就等于 abc这条路径上所有字符的出现次数，其他的也同理。

• abc的前缀分数和为 2 + 2 + 1 = 5
• ab的前缀分数和为 2 + 2 = 4
• bc的前缀分数和为 2 + 1 = 3
• b的前缀分数和为 2
• …

时间复杂度： O(L)O(L)O(L)

C++代码：

class Solution {
public:vector sumPrefixScores(vector& words) {struct Node{Node* children[26] = {};int cnt = 0;};Node* root = new Node();for(auto &s:words){auto node = root;for(auto c:s){int idx = c  -'a';if(node->children[idx] == nullptr) node->children[idx] = new Node();node = node->children[idx];node->cnt++;}}int n = words.size();vector ans(n);for(int i = 0;i < n;i++){auto node = root;for(auto c:words[i]){int idx = c  -'a';if(node->children[idx] != nullptr){node = node->children[idx];ans[i] += node->cnt;}else break;}}return ans;}
};

Java代码：

class Solution {Trie root = new Trie();private void insert(String s){Trie node = root;for(var c:s.toCharArray()){int idx = c - 'a';if(node.childern[idx] == null) node.childern[idx] = new Trie();node = node.childern[idx];node.cnt++;}}private int get(String s){Trie node = root;int ans = 0;for(var c:s.toCharArray()){int idx = c  -'a';if(node.childern[idx] != null){node = node.childern[idx];ans += node.cnt;}else break;}return ans;}public int[] sumPrefixScores(String[] words) {int n = words.length;int[] ans = new int[n];for(int i = 0;i < n;i++) insert(words[i]);for(int i = 0;i < n;i++){ans[i] = get(words[i]);}return ans;}
}class Trie{int cnt;Trie[] childern;Trie(){cnt = 0;childern = new Trie[26];}
}