1160. 拼写单词

🟢   🔖  数组 哈希表 字符串 计数  🔗 力扣 LeetCode

题目

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"

Output: 6

Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"

Output: 10

Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] and chars consist of lowercase English letters.

题目大意

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和 。

示例 1：

输入： words = ["cat","bt","hat","tree"], chars = "atach"

输出： 6

解释：

可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入： words = ["hello","world","leetcode"], chars = "welldonehoneyr"

输出： 10

解释：

可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• 所有字符串中都仅包含小写英文字母

解题思路

1. 统计字母表中每个字母的数量
   通过统计 chars 中每个字母出现的次数，生成一个字符频率的哈希表。

2. 判断每个单词是否能拼写
   对于 words 中的每个单词，统计该单词中每个字母的需求数量，然后检查 chars 中是否有足够的字母来拼写该单词。如果能够拼写，累加该单词的长度。

3. 累加所有能够拼写的单词的长度
   遍历所有单词并检查是否能拼写，累加能够拼写的单词的长度。

复杂度分析

• 时间复杂度：O(n + k * m)
  • 遍历 chars 字符串并统计字符频率需要 O(n)，其中 n 是 chars 的长度。
  • 统计 k 个单词的字符频率需要 O(k * m)，其中 k 是 words 的长度，m 是单词的平均长度。
  • 总的时间复杂度为 O(n + k * m)。
• 空间复杂度：O(n + k * m)，使用两个 Map 存储 chars 和每个单词的字符频率。

代码

var countCharacters = function (words, chars) {
	let charsMap = new Map();

	// 统计 chars 中每个字母出现的次数
	for (let char of chars) {
		charsMap.set(char, (charsMap.get(char) || 0) + 1);
	}

	let totalLength = 0;

	// 遍历 words 中的每个单词
	for (let word of words) {
		let wordMap = new Map();
		let canForm = true;

		for (let char of word) {
			// 统计当前单词中每个字母的需求数量
			wordMap.set(char, (wordMap.get(char) || 0) + 1);
			// 检查 chars 中是否有足够的字母
			if (cur.get(char) > (charsMap.get(char) || 0)) {
				canForm = false;
				break;
			}
		}

		// 如果能拼写这个单词，累加它的长度
		if (canForm) {
			totalLength += word.length;
		}
	}

	return totalLength;
};

相关题目

题号	标题	题解	标签	难度	力扣
383	赎金信	[✓]	哈希表 字符串 计数	🟢	🀄️ 🔗
2287	重排字符形成目标字符串	[✓]	哈希表 字符串 计数	🟢	🀄️ 🔗