2416.md

title	description	keywords
2416. 字符串的前缀分数和	LeetCode 2416. 字符串的前缀分数和题解，Sum of Prefix Scores of Strings，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2416. 字符串的前缀分数和 字符串的前缀分数和 Sum of Prefix Scores of Strings 解题思路 字典树 数组 字符串 计数

2416. 字符串的前缀分数和

🔴 Hard  🔖  字典树 数组 字符串 计数  🔗 力扣 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" is 2, 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+	🟠	🀄️ 🔗