赎金信

约 641 字大约 2 分钟

2025-02-26

383. 赎金信

给你两个字符串：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 <= 105
ransomNote 和 magazine 由小写英文字母组成

如果 ransomNote 的长度大于 magazine 的长度，则无法构造，直接返回 false。创建一个长度为 26 的数组，用于记录 magazine 中每个字母的出现次数，遍历 magazine 中的每个字符，统计每个字母出现的次数，遍历 ransomNote 中的每个字符，检查是否可以从 magazine 中取出这些字符，每取出一个字符，对应字母的计数减 1，如果某个字母的计数小于 0，说明 magazine 中该字母不够用，返回 false。如果遍历完成后，没有返回 false，则说明 ransomNote 可以由 magazine 构造

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 重点。因为magazine中的字符只能用一次，所以如果 ransomNote 的长度大于 magazine 的长度，则无法构造，直接返回 false
        if (ransomNote.length() > magazine.length()) {
            return false;
        }

        // 因为都是小写字母，所以创建一个长度为 26 的数组，用于记录 magazine 中每个字母的出现次数
        int[] cnt = new int[26];
        // 遍历 magazine 中的每个字符，统计每个字母出现的次数，这是库存。
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }

        // 遍历 ransomNote 中的每个字符，检查是否可以从 magazine 中取出这些字符
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--; // 每取出一个字符，库存减 1。重点。
            if (cnt[c - 'a'] < 0) {
                // 如果某个字母的计数小于 0，说明 magazine 中该字母不够用，返回 false
                return false;
            }
        }

        // 如果遍历完成后，没有返回 false，则说明 ransomNote 可以由 magazine 构造
        return true;
    }
}

时间复杂度： $O(m+n)$ ，其中 $m$ 是字符串 ransomNote 的长度， $n$ 是字符串 magazine 的长度，我们只需要遍历两个字符一次即可。注意时间复杂度不是直接取所有独立操作的最大值，而是把独立操作的时间复杂度相加后保留最大值。
空间复杂度： $O(|S|) ， S$ 是字符集，这道题中 $S$ 为全部小写英语字母，因此 $|S|=26$ 。

赎金信

383. 赎金信

数组，先构造再消费