383. 赎金信

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

题目

Given two strings ransomNote and magazine, return true ifransomNotecan be constructed by using the letters frommagazine andfalseotherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b"

Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"

Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"

Output: true

Constraints:

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote and magazine consist of lowercase English letters.

题目大意

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路

1. 使用哈希表记录每个字符的出现次数：遍历杂志字符串，使用哈希表记录每个字符的出现次数。

2. 检查赎金信中的字符：遍历赎金信字符串，对于每个字符，查看哈希表中是否存在该字符并且出现次数大于零，如果是，则减少对应字符的出现次数；如果不是，则返回 false。

3. 返回结果：如果遍历结束，说明赎金信中的每个字符在杂志中都出现了足够次数，返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(N + M)，其中 N 和 M 分别是赎金信和杂志的长度。
• 空间复杂度：O(K)，其中 K 是字符集的大小，这里假设字符集是有限的，通常是常数大小。

代码

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
	let map = new Map();

	// 记录杂志中每个字符的出现次数
	for (let i of magazine) {
		const num = map.get(i) || 0;
		map.set(i, num + 1);
	}

	// 检查赎金信中的字符
	for (let i of ransomNote) {
		const num = map.get(i) || 0;
		if (num == 0) return false;
		map.set(i, num - 1);
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度
691	贴纸拼词		位运算 数组 字符串 3+
1160	拼写单词		数组 哈希表 字符串 1+