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。注意，magazine 里的每个字母只能用一次，而且只有小写字母。

比如：

• ransomNote = "a", magazine = "b" → 不行，因为 magazine 里没有 a。
• ransomNote = "aa", magazine = "ab" → 也不行，因为 magazine 里只有一个 a，但你需要两个。
• ransomNote = "aa", magazine = "aab" → 可以，因为 magazine 里有两个 a，正好够用。

思路是怎么来的

想象一下，你有一堆字母积木（就是 magazine 里的字母），你想搭出另一个单词（ransomNote）。你只能从积木堆里拿，每个积木只能用一次。那你怎么检查够不够呢？

最直接的办法：先把积木堆里的每种字母数清楚——比如 a 有几个、b 有几个……然后，你要搭的单词里需要什么字母、各需要几个，你就去积木堆里扣。如果某个字母不够扣了（比如你需要 3 个 a，但积木堆只有 2 个），那就不行。

所以思路就是两步： 1. 数一数 `magazine` 里每种字母有多少个。 2. 遍历 `ransomNote`，每需要一个字母，就从对应的计数里减 1。如果减到负数，说明不够了，直接说“不行”。

因为只有 26 个小写字母，我们可以用一个长度为 26 的数组来当计数器。数组的索引 0 对应 a，1 对应 b，……，25 对应 z。这样，每个字母的计数就是 cnt[字母 - 'a']。

代码逐步拆解

我们来看参考代码（Java），一行一行解释：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 1. 创建一个计数器数组，长度 26，初始全是 0
        int[] cnt = new int[26];

        // 2. 先统计 magazine 里每个字母出现的次数
        for (char c : magazine.toCharArray()) {
            // c - 'a' 得到索引：比如 'a' 是 0，'b' 是 1，...
            cnt[c - 'a']++;
        }

        // 3. 再遍历 ransomNote，检查每个字母够不够
        for (char c : ransomNote.toCharArray()) {
            // 每遇到一个字母，就把对应的计数减 1（表示用掉了一个）
            cnt[c - 'a']--;

            // 如果减完之后发现计数小于 0，说明 magazine 里这个字母不够用了
            if (cnt[c - 'a'] < 0) {
                return false; // 直接返回 false
            }
        }