LeetCode 383. 赎金信
题目描述
✅ 383. 赎金信
题意分析
从
magazine中取出字符组成ransomNote，杂志中的每次字符出现只能使用一次，但字符顺序可以重新安排，多余字符也可以不用。两串都只含小写英文字母。
解法：字符计数
核心思路
[!blue]
顺序不受限制，只需判断每一种字母的数量是否足够，不需要查找子串或子序列。因为只有 26 种字母，用固定长度的数组就能保存全部库存，字符
ch对应下标ch - 'a'。先统计
magazine，再逐字扫描ransomNote。每使用一个字母，就将对应计数减一。因此扫描过程中，cnt[c]始终等于杂志中字母c的数量减去已经处理的赎金信中字母c的数量。如果某个计数变成负数，说明这个字母的需求已经超过全部库存；其他字母不能替代它，后续扫描也只会继续消耗，可以立即返回失败。若全部字符都处理完且没有负数，就为每个需求分配到了一个未使用的来源字符，返回成功。计数为 0 只表示恰好用完，材料也不必全部用完。
解题步骤
- 创建长度为 26 的零值计数数组。
- 扫描
magazine，增加各字母的可用次数。- 扫描
ransomNote，每遇到一个字母就消耗一次，计数小于 0 时返回false。- 扫描结束返回
true，不再要求剩余计数全为 0。
代码实现
// 遍历 ransomNote，每用掉一个字母就递减计数，若出现负数说明无法构成。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] cnt = new int[26];
for (int i = 0; i < magazine.length(); i++) {
cnt[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
int idx = ransomNote.charAt(i) - 'a';
cnt[idx]--;
// 零是恰好用光，负数才表示材料不足
if (cnt[idx] < 0) {
return false;
}
}
return true;
}
}
// 遍历 ransomNote，每用掉一个字母就递减计数，若出现负数说明无法构成。
func canConstruct(ransomNote string, magazine string) bool {
var cnt [26]int
for i := 0; i < len(magazine); i++ {
cnt[magazine[i]-'a']++
}
for i := 0; i < len(ransomNote); i++ {
idx := ransomNote[i] - 'a'
cnt[idx]--
// 零是恰好用光，负数才表示材料不足
if cnt[idx] < 0 {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：$O(m+n)$，
m、n分别为两个字符串的长度，各扫描一次。- 空间复杂度：$O(1)$，固定字母频次表。
关键点总结
[!green]
- 材料允许剩余，只需覆盖需求。
- 库存为零与库存为负意义不同。
- 26 个计数分别记录每种字母的数量，重复字符也会被完整计入。
易错点总结
[!yellow]
- 恰好用光就失败，会错误拒绝一对一匹配。
- 只看字母是否出现，不能满足重复需求。
- 把材料和需求方向交换，会检查反向包含关系；应先统计
magazine，再消耗ransomNote。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 242. 有效的字母异位词 | 简单 | 原题要求两侧频次完全相同，本题只要求来源字符频次足以覆盖目标需求。 |
| 76. 最小覆盖子串 | 困难 | 同样检查字符多重集合覆盖，原题还要在长串中找最短覆盖窗口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！