leetcode 面试经典 150 题：赎金信
| 链接 | 赎金信 |
|---|---|
| 题序号 | 383 |
| 题型 | 字符串 |
| 解题方法 | 哈希表（数组计数法） |
| 难度 | 简单 |
| 熟练度 | ✅✅✅ |
题目
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true提示：
1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成
题解
-
算法剖析：使用哈希表来统计magazine中每个字符的出现次数，然后遍历ransomNote，检查每个字符在magazine中的剩余次数是否足够。具体步骤如下：
- 使用一个大小为26的数组（或哈希表）来统计magazine中每个字符的出现次数。
- 遍历ransomNote中的每个字符，对应在数组中减去该字符的计数。
- 如果在任何时候，数组中对应字符的计数小于0，则返回false，表示ransomNote不能由magazine构成。
- 如果遍历结束后没有字符计数小于0，则返回true。
-
算法复杂度：时间复杂度为O(n + m)，其中n是ransomNote的长度，m是magazine的长度，空间复杂度为O(1)，因为只使用了一个固定大小的数组来存储字符计数。
-
c++ 实现算法：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// 创建一个大小为 26 的数组来记录每个字母的频次（假设字符都是小写字母）
vector<int> magazineCount(26, 0);
// 填充 magazineCount，统计 magazine 中每个字母的出现次数
for (char c : magazine) {
magazineCount[c - 'a']++;
}
// 遍历 ransomNote，检查 magazine 中是否有足够的字母
for (char c : ransomNote) {
int index = c - 'a';
if (magazineCount[index] > 0) {
magazineCount[index]--; // 使用一个字符
} else {
return false; // 如果没有足够的字符，返回 false
}
}
return true; // 如果所有字符都满足，返回 true
}
};
- 推演过程：
假设有以下输入：
ransomNote = “aa” magazine = “aab” 我们使用一个数组 magazineCount 来记录 magazine
中每个字母的出现次数，使用一个循环来遍历 ransomNote 的每个字母，检查 magazineCount 中是否有足够的字母。步骤 1：初始化 magazineCount 数组 首先，我们需要一个大小为 26 的数组来存储 magazine
中每个字母的频次（因为字母表中只有 26 个字母，且假设字符都是小写字母）。 vector magazineCount(26,
0); magazineCount 数组初始化为： magazineCount = [0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]步骤 2：填充 magazineCount 数组 然后，我们遍历 magazine 字符串，统计每个字母出现的次数，并将计数存入 magazineCount 数组。 magazine = “aab”
遍历 magazine 中的字符： 对于字符 ‘a’，它对应的索引是 0，所以 magazineCount[0] 增加 1。 对于字符
‘a’，它对应的索引是 0，所以 magazineCount[0] 再增加 1。 对于字符 ‘b’，它对应的索引是 1，所以magazineCount[1] 增加 1。
magazineCount 数组更新为： magazineCount = [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]步骤 3：遍历 ransomNote 并检查是否能构建 接下来，我们遍历 ransomNote 字符串，检查 magazineCount 中是否有足够的字母。 ransomNote = “aa” 我们需要检查是否可以从 magazineCount 中提取出两个 ‘a’ 字符。
- 第一轮（检查 ransomNote[0] = ‘a’）： index = ‘a’ - ‘a’ = 0，即 index = 0。 检查 magazineCount[0]，当前值是 2，表示 magazine 中有 2 个 ‘a’ 字符，足够使用一个。 使用一个 ‘a’，将 magazineCount[0] 减 1，变为 1。
- 第二轮（检查 ransomNote[1] = ‘a’）： index = ‘a’ - ‘a’ = 0，即 index = 0。 检查 magazineCount[0]，当前值是 1，表示 magazine 中还有 1 个 ‘a’ 字符，足够使用一个。 使用一个 ‘a’，将 magazineCount[0] 减 1，变为 0。
步骤 4：返回结果 遍历完 ransomNote 中的所有字符后，我们已经从 magazine 中成功提取出所有需要的字符。因此，返回 true。
最终的 magazineCount 数组是：
magazineCount = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0] 这表示 magazine 中的 ‘a’ 字符已经被完全使用，而 ‘b’ 字符剩余 1 个，其他字符没有使用。
- 完整demo：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// 创建一个大小为 26 的数组来记录每个字母的频次（假设字符都是小写字母）
vector<int> magazineCount(26, 0);
// 填充 magazineCount，统计 magazine 中每个字母的出现次数
for (char c : magazine) {
magazineCount[c - 'a']++;
}
// 遍历 ransomNote，检查 magazine 中是否有足够的字母
for (char c : ransomNote) {
int index = c - 'a';
if (magazineCount[index] > 0) {
magazineCount[index]--; // 使用一个字符
} else {
return false; // 如果没有足够的字符，返回 false
}
}
return true; // 如果所有字符都满足，返回 true
}
};
int main() {
Solution solution;
// 测试用例
string ransomNote = "aa";
string magazine = "aab";
// 输出结果
if (solution.canConstruct(ransomNote, magazine)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
原文地址：https://blog.csdn.net/yanceyxin/article/details/144835787
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！