LeetCode 383简单哈希计数
赎金信 图解题解
这道题到底在问什么
给两个字符串 ransomNote 和 magazine，判断 ransomNote 能否由 magazine 里的字母拼出。magazine 里每个字母只能用一次。
- ransomNote
- "aabb"
- magazine
- "baabba"
- 输出
- true
最优解：一步一步想明白
- 3两步走：先数杂志建库存表，再拿赎金信逐字去库存里领。领得到就减一，领不到就 false。
- 4先把注意力放在杂志上。从左到右数一遍，每个字母出现几次就记进库存表。
- 5指针走到杂志下标 0，这一格是 'b'。把它记一笔进库存。
- 6'b' 的库存加一，现在是 1（高亮那行就是刚更新的）。
- 7指针走到杂志下标 1，这一格是 'a'。把它记一笔进库存。
- 8'a' 的库存加一，现在是 1（高亮那行就是刚更新的）。
- 9指针走到杂志下标 2，这一格是 'a'。把它记一笔进库存。
- 10'a' 的库存加一，现在是 2（高亮那行就是刚更新的）。
- 11指针走到杂志下标 3，这一格是 'b'。把它记一笔进库存。
- 12'b' 的库存加一，现在是 2（高亮那行就是刚更新的）。
- 13指针走到杂志下标 4，这一格是 'b'。把它记一笔进库存。
- 14'b' 的库存加一，现在是 3（高亮那行就是刚更新的）。
- 15指针走到杂志下标 5，这一格是 'a'。把它记一笔进库存。
- 16'a' 的库存加一，现在是 3（高亮那行就是刚更新的）。
- 17杂志全数完了，库存表建好：a 有 3 个、b 有 3 个。接下来拿赎金信来领字母。
- 18轮到赎金信第 0 个字母 'a'。先到库存表查一下 'a' 还剩 3 个。
- 19领到了！把 'a' 的库存减一，现在剩 2 个。继续看下一个字母。
- 20轮到赎金信第 1 个字母 'a'。先到库存表查一下 'a' 还剩 2 个。
- 21领到了！把 'a' 的库存减一，现在剩 1 个。继续看下一个字母。
- 22轮到赎金信第 2 个字母 'b'。先到库存表查一下 'b' 还剩 3 个。
- 23领到了！把 'b' 的库存减一，现在剩 2 个。继续看下一个字母。
- 24轮到赎金信第 3 个字母 'b'。先到库存表查一下 'b' 还剩 2 个。
- 25领到了！把 'b' 的库存减一，现在剩 1 个。继续看下一个字母。
- 26赎金信 "aabb" 的每个字母都从库存里顺利领到了，杂志够拼，返回 true。
⚠️ 容易写错的地方
✗ 错：把两个字符串各排序后逐位比
✓ 对：用计数表只数一遍
排序是 O(n log n)，计数表 O(n) 更快；而且本题只需「够不够」，不需要顺序
✗ 错：领字母时忘了检查库存是否为 0 就直接减
✓ 对：先判 cnt[ch] <= 0 再减
不检查会减成负数，把「不够」误判成「够」
✗ 错：先减库存再判断
✓ 对：先查后减
顺序反了会在库存恰好为 0 时漏掉 false 的情况
完整代码（Python / C++ / Java）
Python
def canConstruct(ransomNote, magazine):
from collections import Counter
cnt = Counter(magazine) # 数杂志，建库存
for ch in ransomNote: # 逐字去领
if cnt[ch] <= 0: # 库存不够
return False
cnt[ch] -= 1 # 领走一个
return TrueC++
bool canConstruct(string ransomNote, string magazine){
int cnt[26] = {0};
for (char c : magazine) cnt[c-'a']++;
for (char c : ransomNote) {
if (cnt[c-'a'] <= 0) return false;
cnt[c-'a']--;
}
return true;
}Java
public boolean canConstruct(String ransomNote, String magazine) {
int[] cnt = new int[26];
for (char c : magazine.toCharArray()) cnt[c-'a']++;
for (char c : ransomNote.toCharArray()) {
if (cnt[c-'a'] <= 0) return false;
cnt[c-'a']--;
}
return true;
}复杂度
时间
O(m + n)
m 是杂志长度、n 是赎金信长度，各扫一遍
空间
O(1)
计数表最多 26 个小写字母，是常数大小
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 赎金信 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不用排序两个字符串再比？+
排序是 O(n log n)，而计数表只要 O(n)。而且本题不关心字母顺序、只关心数量够不够，计数表正好对口。
如果字符不止小写字母（比如有大写、数字）怎么办？+
把固定的 26 长度数组换成哈希表 dict/Counter 即可，逻辑完全不变：数 magazine 建库存，拿 ransomNote 逐字去领。
和「有效的字母异位词」有什么关系？+
几乎是同一套计数表手法。异位词要求两边数量「完全相等」，赎金信只要求一边「不超过」另一边，判定条件松一点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 赎金信 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。