赎金信 | LeetCode-383 | 哈希集合

在字符串中，如果能使用哈希集合，那么大概率也能使用哈希数组

---

LeetCode链接：383. 赎金信

---

1.题目描述

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

2.题解

2.1 哈希集合

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 创建一个哈希表用于存储 magazine 中每个字符出现的次数
        Map<Character, Integer> map = new HashMap<>();

        // 遍历 magazine 字符串，将每个字符的出现次数记录到哈希表中
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);  // 获取当前字符
            map.put(c, map.getOrDefault(c, 0) + 1);  // 更新字符出现的次数
        }

        // 遍历 ransomNote 字符串，检查每个字符是否能够从 magazine 中取出
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);  // 获取当前字符
            map.put(c, map.getOrDefault(c, 0) - 1);  // 将字符在哈希表中的计数减1
        }

        // 遍历哈希表，检查是否有字符的计数为负数
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for (Map.Entry<Character, Integer> entry : entries) {
            if (entry.getValue() < 0)  // 如果某个字符的计数为负数，说明 ransomNote 中需要的该字符多于 magazine 提供的字符
                return false;  // 返回 false 表示无法构造
        }

        // 如果所有字符的计数都不为负数，返回 true 表示可以构造
        return true;
    }
}

2.2 哈希数组

• 由于这道题目具有特殊性，只有小写字母，所有转化成哈希数组来做

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 创建一个大小为26的数组来记录magazine中每个字母的出现次数
        int[] charCounts = new int[26];

        // 遍历magazine字符串，将每个字符的出现次数记录到数组中
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            charCounts[c - 'a']++;
        }

        // 遍历ransomNote字符串，检查每个字符是否能够从magazine中取出
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            charCounts[c - 'a']--;
            if (charCounts[c - 'a'] < 0) {
                // 如果某个字符的计数变为负数，说明magazine中的该字符数量不足
                return false;
            }
        }

        // 如果所有字符的数量都足够，返回true
        return true;
    }
}