跳至主要內容

2416. 字符串的前缀分数和


2416. 字符串的前缀分数和open in new window

🔴   🔖  字典树 数组 字符串 计数  🔗 力扣open in new window LeetCodeopen in new window

题目

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添加与搜索单词 - 数据结构设计open in new window[✓]深度优先搜索 设计 字典树 1+
421数组中两个数的最大异或值open in new window位运算 字典树 数组 1+
677键值映射open in new window设计 字典树 哈希表 1+