华为 OD 训练营 · 题解精讲
LC383. 赎金信（HJ81. 字符串字符匹配）
LC383. 赎金信（HJ81. 字符串字符匹配） 视频地址。
题目描述
给你两个字符串：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 <= 10^5 ransomNote 和 magazine 由小写英文字母组成
题目解析
解题思路
本题判断 ransomNote 能否由 magazine 中的字符构成，本质是检查 magazine 中每个字符的出现次数是否都 ≥ ransomNote 中对应字符的出现次数。由于字符集仅为 26 个小写字母，可以使用固定大小的数组作为哈希表来统计频次，这是最直接高效的做法。
核心思想：先统计 magazine 中各字母的出现次数（存入数组），再遍历 ransomNote，每遇到一个字母就将对应计数减 1，若某字母计数变为负数，说明 magazine 中该字母不够用，返回 false。
关键步骤
1. 初始化计数器：创建长度为 26 的整型数组 cnt，初始值全为 0，cnt[0] 对应 'a'，cnt[1] 对应 'b'，以此类推。 2. 统计 magazine：遍历 magazine 字符串，对每个字符 ch，计算索引 idx = ord(ch) - ord('a')，将 cnt[idx] 加 1。 3. 验证 ransomNote：遍历 ransomNote，对每个字符 ch，将 cnt[ord(ch) - ord('a')] 减 1，并立即检查该值是否 < 0。若 < 0 则返回 false。 4. 返回结果：若遍历完 ransomNote 未触发 false，则返回 true。
示意图（以 magazine = "aab", ransomNote = "aa" 为例）：
初始 cnt: [0,0,0,...]
magazine 统计后: [2,1,0,...] (a:2, b:1)
遍历 ransomNote:
'a' → cnt[0]=1 (≥0)
'a' → cnt[0]=0 (≥0)
结束 → true复杂度分析
- 时间复杂度：O(n + m)，其中 n 和 m 分别为
ransomNote和magazine的长度。需要遍历两个字符串各一次，数组操作均为 O(1)。 - 空间复杂度：O(1)，只使用了固定大小（26）的数组，与输入规模无关。
参考代码
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 手动设置哈希表
# 这里的哈希表的作用是计数器
# 由于小写字母的个数为 26 个，所以数组大小为 26
cnt = [0] * 26
# 记录 magazine 里字母出现的次数
for ch in magazine:
# 对于数组类型，其下标为 int 类型
# 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
# 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次
idx = ord(ch) - ord('a')
cnt[idx] += 1
# 再用 ransomNote 去验证这个数组是否包含了 ransomNote 所需要的所有字母
for ch in ransomNote:
# 在遍历过程中，每遍历一个字母，对应的频次减 1
cnt[ord(ch) - ord('a')] -= 1
# 如果发现某个字母的频次小于了 0
# 说明在 ransomNote 中出现了 magazine 未曾有的字母
# 即 ransomNote 不能由 magazine 里面的字符构成
if cnt[ord(ch) - ord('a')] < 0 :
return False
# 说明可以，返回 true
return True