2416. 字符串的前缀分数和
2416. 字符串的前缀分数和
🔴 🔖 字典树
数组
字符串
计数
🔗 力扣
LeetCode
题目
You are given an array words
of size n
consisting 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"
is2
, since"ab"
is a prefix of both"ab"
and"abc"
.
Return an arrayanswer
of sizen
whereanswer[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 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i]
consists of lowercase English letters.
题目大意
给你一个长度为 n
的数组 words
,该数组由 非空 字符串组成。
定义字符串 word
的 分数 等于以 word
作为 前缀 的 words[i]
的数目。
- 例如,如果
words = ["a", "ab", "abc", "cab"]
,那么"ab"
的分数是2
,因为"ab"
是"ab"
和"abc"
的一个前缀。
返回一个长度为 n
的数组 answer
,其中 answer[i]
是 words[i]
的每个非空前缀的分数 总和 。
注意:字符串视作它自身的一个前缀。
解题思路
可以用字典树存储所有字符串,由于每个节点都是其子树节点的前缀,题干中的分数就是在字符串插入字典树的过程中,经过该节点的字符串个数,即以该节点为前缀的字符串的个数。
插入后,再次遍历每个字符串,在字典树上查找,累加路径上的分数之和就是答案。
代码
/**
* @param {string[]} words
* @return {number[]}
*/
var sumPrefixScores = function (words) {
let map = {};
for (let word of words) {
let obj = map;
for (let char of word) {
if (!obj[char]) {
obj[char] = {};
obj[char].count = 0;
}
obj[char].count++;
obj = obj[char];
}
}
let res = [];
for (let word of words) {
let sum = 0,
obj = map;
for (let char of word) {
sum += obj[char].count;
obj = obj[char];
}
res.push(sum);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
211 | 添加与搜索单词 - 数据结构设计 | [✓] | 深度优先搜索 设计 字典树 1+ | |
421 | 数组中两个数的最大异或值 | 位运算 字典树 数组 1+ | ||
677 | 键值映射 | 设计 字典树 哈希表 1+ |