题目描述
思路解析动画文字版
两步走:先数杂志建库存表,再拿赎金信逐字去库存里领。领得到就减一,领不到就 false。
先把注意力放在杂志上。从左到右数一遍,每个字母出现几次就记进库存表。
指针走到杂志下标 0,这一格是 'b'。把它记一笔进库存。
'b' 的库存加一,现在是 1(高亮那行就是刚更新的)。
指针走到杂志下标 1,这一格是 'a'。把它记一笔进库存。
'a' 的库存加一,现在是 1(高亮那行就是刚更新的)。
指针走到杂志下标 2,这一格是 'a'。把它记一笔进库存。
'a' 的库存加一,现在是 2(高亮那行就是刚更新的)。
指针走到杂志下标 3,这一格是 'b'。把它记一笔进库存。
'b' 的库存加一,现在是 2(高亮那行就是刚更新的)。
指针走到杂志下标 4,这一格是 'b'。把它记一笔进库存。
'b' 的库存加一,现在是 3(高亮那行就是刚更新的)。
指针走到杂志下标 5,这一格是 'a'。把它记一笔进库存。
'a' 的库存加一,现在是 3(高亮那行就是刚更新的)。
杂志全数完了,库存表建好:a 有 3 个、b 有 3 个。接下来拿赎金信来领字母。
轮到赎金信第 0 个字母 'a'。先到库存表查一下 'a' 还剩 3 个。
领到了!把 'a' 的库存减一,现在剩 2 个。继续看下一个字母。
轮到赎金信第 1 个字母 'a'。先到库存表查一下 'a' 还剩 2 个。
领到了!把 'a' 的库存减一,现在剩 1 个。继续看下一个字母。
轮到赎金信第 2 个字母 'b'。先到库存表查一下 'b' 还剩 3 个。
领到了!把 'b' 的库存减一,现在剩 2 个。继续看下一个字母。
轮到赎金信第 3 个字母 'b'。先到库存表查一下 'b' 还剩 2 个。
领到了!把 'b' 的库存减一,现在剩 1 个。继续看下一个字母。
赎金信 "aabb" 的每个字母都从库存里顺利领到了,杂志够拼,返回 true。
三个边界:信比杂志长必假、空信必真、缺某字母必假。
三个高频追问:为何不排序、字符集变大怎么改、和异位词的异同。
参考代码
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 True复杂度
- 时间:O(m + n),m 是杂志长度、n 是赎金信长度,各扫一遍
- 空间:O(1),计数表最多 26 个小写字母,是常数大小
易错点
面试追问把动画讲成自己的话
追问为什么不用排序两个字符串再比?
追问如果字符不止小写字母(比如有大写、数字)怎么办?
追问和「有效的字母异位词」有什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
根据字符出现频率排序
LeetCode 451 · 中等 · 沿着 哈希计数套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题