LeetCode 383. 赎金信

约 7 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 华为 面试经典 150 题
标签
字符串 哈希表 计数
目录

题目描述

✅ 383. 赎金信

题意分析

给两个字符串，问能否从 magazine 里剪下若干字符，拼出 ransomNote。magazine 中的每个字符只能被用一次。

这里有两个容易被忽略的点。第一，题目不要求保持顺序——剪下来的字符可以任意排列，所以本质上比较的是「每种字符各有多少个」，而不是子串或子序列关系。第二，「每个字符只能用一次」意味着比较的是数量而不是种类，仅仅判断 magazine 是否包含 ransomNote 用到的所有字母是不够的。

约束里明确两个字符串都只由小写英文字母构成，长度上限是 $10^5$。字符集只有 $26$ 个是个很强的信号：可以用定长数组代替哈希表，索引直接由字符减去 'a' 得到。

边界方面：ransomNote 为空时答案恒为真；ransomNote 比 magazine 长时必然为假（不过这个特判不是必需的，计数逻辑会自动覆盖）；两串完全相同时为真。

解法：字符计数

核心思路

最朴素的做法是对 ransomNote 的每个字符，去 magazine 里线性查找一个未被使用的相同字符并打上标记，这是 $O(mn)$。另一种思路是把两串各自排序后用双指针匹配，能降到 $O(m\log m + n\log n)$，但排序的开销完全没必要。

瓶颈在于反复扫描 magazine 找同一个字符。既然顺序无关，真正需要的信息只有「magazine 里每种字母各有几个」这 $26$ 个数字。把这个统计一次性做完，后续每次查询就退化成一次数组下标访问。

于是维护一个长度为 $26$ 的计数数组 cnt，先用 magazine 填满。接着扫描 ransomNote，每遇到一个字符就把对应计数减一，并检查是否变成负数。这里的不变量是：扫描到 ransomNote 的第 $i$ 个字符之前，cnt[c] 恰好等于「magazine 中字符 $c$ 的总数」减去「ransomNote 前 $i$ 个字符中 $c$ 的个数」，也就是该字符的剩余可用库存。库存一旦被扣成负数，就说明需求超过了供给，可以立即返回假。

之所以能在发现负数时立刻返回，是因为各字符的库存互相独立，某一种字符不够用，再往后看别的字符也无法弥补。

解题步骤

  • 开一个长度为 $26$ 的整型数组作为计数器，元素默认全为 $0$。用定长数组而非哈希表，是因为字符集已知且极小，数组的访问常数远低于哈希。
  • 遍历 magazine，对每个字符执行 cnt[ch - 'a']++。减去 'a' 把 'a' 到 'z' 映射到 $0$ 到 $25$，这是小写字母题最常用的索引方式。
  • 遍历 ransomNote，先算出当前字符的索引，执行减一，再判断该位置是否小于 $0$。顺序是「先减后判」而不是「先判后减」：先减后判只需要一次数组读写和一次比较，逻辑也更短。
  • 一旦某个位置减成负数就直接返回假。此时不需要继续扫描，因为字符之间不存在互相替代的可能，缺口无法被后续字符弥补。
  • 循环完整走完仍未出现负数，说明每种字符的需求都在库存之内，返回真。

以 ransomNote = "aab"、magazine = "baa" 走一遍：先统计 magazine，扫到 'b' 使 cnt[1] 变为 $1$，扫到第一个 'a' 使 cnt[0] 变为 $1$，扫到第二个 'a' 使 cnt[0] 变为 $2$，此时库存为 a 两个、b 一个。接着扫 ransomNote：第一个字符 'a'，cnt[0] 减为 $1$，不小于 $0$，继续；第二个字符 'a'，cnt[0] 减为 $0$，仍不小于 $0$，继续——注意这里恰好用光但没有超支，所以不能用「等于 $0$」作为失败条件；第三个字符 'b'，cnt[1] 减为 $0$，同样合法。循环结束返回真，与直觉一致，"baa" 重排后正好是 "aab"。再看一个反例，ransomNote = "aa"、magazine = "ab"：统计后 cnt[0] 为 $1$、cnt[1] 为 $1$；扫 ransomNote 的第一个 'a' 时 cnt[0] 减为 $0$ 通过，第二个 'a' 时 cnt[0] 减为 $-1$，触发提前返回假。

代码实现

// 遍历 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$ 分别是 magazine 与 ransomNote 的长度。两次独立的线性扫描，每个字符只做一次减法定位和一次数组读写，中途提前返回只会更快。
  • 空间复杂度：$O(1)$。计数数组长度固定为 $26$，由字符集大小决定，与两个字符串的长度无关。

关键点总结

  • 顺序无关的匹配问题，本质是多重集合的包含关系。识别出这一点后，问题立刻从「查找」降级为「计数」，复杂度也从乘积级降到线性。
  • 字符集有限且已知时，定长数组优于哈希表。索引由字符减去基准字符得到，既省去哈希开销，也让空间复杂度落到常数。
  • 「先减后判负」这个小写法值得记住：它把「够不够用」的判断统一成一个符号检查，比先取值、再比较、再回写要短，也不容易写出差一错误。
  • 各字符库存互相独立，因此发现任一字符透支即可立刻返回。能说清「为什么可以提前退出」，是把模板题答出深度的关键。
  • 面试视角：这题几乎必被追问「如果字符集扩大到 Unicode 呢」。答案是把定长数组换成哈希表，时间复杂度不变，空间变成 $O(k)$，$k$ 为出现过的不同字符数。
  • 面试视角：另一个常见追问是「和判断字母异位词有什么区别」。异位词要求双向数量完全相等，本题只要求单向不超过，把这层差异说出来能体现审题的细致。

易错点总结

  • 错误写法：把库存判断写成「减到 $0$ 就返回假」 → 对 ransomNote = "a"、magazine = "a"，扣完恰好为 $0$ 是完全合法的，却会返回假，正确答案是真。
  • 错误写法：把判断挪到扣减之前却仍写成 cnt[idx] < 0 → 库存已经是 $0$ 时依然放行，对 ransomNote = "aa"、magazine = "ab" 会一路通过并返回真，正确答案是假。扣减前判断必须用 cnt[idx] <= 0。
  • 错误写法：统计 ransomNote 而扫描 magazine，方向搞反 → 对 ransomNote = "a"、magazine = "aa"，扫到第二个 'a' 时计数减为 $-1$ 返回假，正确答案是真。
  • 错误写法：只判断字符种类是否被覆盖而不比较数量 → 对 ransomNote = "aa"、magazine = "ab" 会认为 a、b 都出现过而返回真，正确答案是假。
  • 错误写法：把两串排序后逐位比较是否相等 → 这实际上在判断异位词，对 ransomNote = "a"、magazine = "ab" 会返回假，正确答案是真。
  • 错误写法：用 magazine.contains(ch) 或 indexOf 判断而不做「用过就划掉」的标记 → 同一个字符会被重复计入，对 "aa" 与 "ab" 返回真，正确答案是假。
  • 错误写法：索引写成 ch 而不是 ch - 'a' → 小写字母的 ASCII 码从 $97$ 起，直接当下标会立刻越界。
  • 错误写法：数组开成 $26$ 却按 ch - 'A' 计算索引 → 小写字母减去 'A' 落在 $32$ 到 $57$ 区间，第一次访问就数组越界。基准字符必须与实际字符集对齐。
  • 错误写法：为了「优化」而先比较两串长度，长度相等时直接返回真 → 长度相等只说明总量匹配，"ab" 与 "aa" 长度相同却无法构成，会误判。
  • 错误写法：每处理一个 ransomNote 字符就重新统计一次 magazine → 复杂度退回 $O(mn)$，在两串长度都是 $10^5$ 的数据下直接超时。

相似题目

题目 难度 考察点
242. 有效的字母异位词 简单 要求两侧数量完全相等，是本题单向包含关系的对称加强版
面试题 01.02. 判定是否互为字符重排 简单 同为重排判定，可先用长度不等快速否定再比计数
LCR 032. 有效的字母异位词 简单 在异位词基础上额外排除两串完全相同的情形
49. 字母异位词分组 中等 计数结果要序列化成哈希键用于分组，重点在键的设计
LCR 033. 字母异位词分组 中等 同一分组任务的另一入口，可对比排序键与计数键的效率差异
面试题 10.02. 变位词组 中等 分组输出顺序不限，适合练习计数键的紧凑编码
387. 字符串中的第一个唯一字符 简单 计数后需要第二遍按原顺序回扫，考察两趟扫描的配合
剑指 Offer 50. 第一个只出现一次的字符 简单 同上但返回字符本身，需处理不存在时的空字符约定
面试题 01.01. 判定字符是否唯一 简单 只关心是否出现过，可用位掩码把计数数组压成一个整数
面试题 01.04. 回文排列 简单 只需统计奇数次字符的个数，考察对计数奇偶性的转化
451. 根据字符出现频率排序 中等 计数之后还要按频次重排输出，需要桶排序或优先队列