📃 题目描述

题目链接：383. 赎金信 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次)

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

你可以假设两个字符串均只含有小写字母。

🔔 解题思路

这题好办，对于快速找字符找数字这种题目，我们应该迅速想到哈希表。

利用一个 map 处理 magazine，key 存储字符，value 存储该字符出现的次数

然后遍历 ransomNote，若某个字符串存在于 map 中，则对应的 value - 1，在减 1 之前，如果 value 已经等于 0 了，意思就是说 magazine 中这个字符的数量已经不足以供 ransomNote 使用了，则立即返回 false；或者，ransomNote 的某个字符串不存在于 map 中，立即返回 false。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine == null || magazine.length() == 0) {
            return true;
        }
        else if (ransomNote == null || ransomNote.length() == 0) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();

        // 利用 map 处理 magazine，key 存储字符，value 存储该字符出现的次数
        for (char ch : magazine.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        // 遍历 ransomNote
        for (char ch : ransomNote.toCharArray()) {
            // ransomNote 的某个字符串不存在于 map 中,立即返回 false
            if (!map.containsKey(ch)) {
                return false;
            }
            // 在减 1 之前,如果 value 已经等于 0 了,则立即返回 false
            if (map.get(ch) == 0) {
                return false;
            }

            map.put(ch, map.get(ch) - 1);
        }

        return true;
    }
}

和 242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 一样，对于哈希表中的 key，如果哈希值比较连续且固定，我们可以用数组的下标来等同。这个题目中的 key 存储的就是 26 个字母，那我们只需要将其转成 int 作为数组的下标即可：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine == null || magazine.length() == 0) {
            return true;
        }
        else if (ransomNote == null || ransomNote.length() == 0) {
            return false;
        }

        int[] nums = new int[26];

        // 利用 map 处理 magazine，key 存储字符，value 存储该字符出现的次数
        for (char ch : magazine.toCharArray()) {
            nums[ch - 'a'] += 1;
        }

        // 遍历 ransomNote
        for (char ch : ransomNote.toCharArray()) {
            // ransomNote 的某个字符串不存在于 map 中,立即返回 false
            // 在减 1 之前,如果 value 已经等于 0 了,则立即返回 false
            if (nums[ch - 'a'] == 0) {
                return false;
            }

            nums[ch - 'a'] -= 1;
        }

        return true;
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)