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" 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+