Leetcode 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

LeetCode链接

解决思路

哈希法

1. 哈希表 charCount：用于统计 magazine 中每个字符的出现次数。
2. 统计 magazine 中字符的出现次数：遍历 magazine 中的每个字符，将其出现次数记录在 charCount 中。
3. 检查 ransomNote 中的字符：遍历 ransomNote 中的每个字符，检查其在 charCount 中是否有足够的数量。如果有，则减少其数量；如果没有，则返回 false。
4. 返回结果：如果 ransomNote 中的所有字符都能在 magazine 中找到足够的数量，则返回 true，否则返回 false。

hash数组法

1. 初始化数组：
   • 使用一个长度为 26 的数组 hash 来统计 magazine 中每个字符的出现次数。数组的索引对应于字符 'a' 到 'z'，即 hash[0] 对应 'a'，hash[1] 对应 'b'，依此类推。
2. 检查长度：
   • 如果 ransomNote 的长度大于 magazine 的长度，直接返回 false。因为 magazine 中的字符数量不足以构成 ransomNote。
3. 统计 magazine 中字符的出现次数：
   • 遍历 magazine 中的每个字符，将其出现次数记录在 hash 数组中。具体来说，对于字符 c，将其出现次数记录在 hash[c - 'a'] 中。
4. 检查 ransomNote 中的字符：
   • 遍历 ransomNote 中的每个字符，检查其在 hash 数组中是否有足够的数量。具体来说，对于字符 c，将其对应的 hash[c - 'a'] 减 1。如果减 1 后 hash[c - 'a'] 小于 0，说明 magazine 中没有足够的字符 c，返回 false。
5. 返回结果：
   • 如果 ransomNote 中的所有字符都能在 magazine 中找到足够的数量，则返回 true，否则返回 false。

code

哈希法

class Solution {

    public boolean canConstruct2(String ransomNote, String magazine) {
        // 创建一个哈希表来统计 magazine 中每个字符的出现次数
        HashMap<Character, Integer> hashMap = new HashMap<>();

        // ramsonNote 的长度大于magazine的长度，直接返回false
        if(ransomNote.length() > magazine.length()){
            return false;
        }

        // 统计 magazine 中每个字符的出现次数
        for (char c : magazine.toCharArray()) {
            hashMap.put(c,hashMap.getOrDefault(c,0) + 1);
        }

        // 检查 ransomNote 中的每个字符是否在 magazine 中有足够的数量
        for (char c : ransomNote.toCharArray()) {
            // 如果 magazine 中没有该字符或数量不足，返回 false
            if(!hashMap.containsKey(c)|| hashMap.get(c) == 0){
                return false;
            }
            // 使用一个字符后，减少其数量
            hashMap.put(c,hashMap.get(c) - 1);
        }

        // 如果所有字符都满足条件，返回 true
        return true;
    }
}

hash数组法

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 初始化hash数组，默认长度26
        int[] hash = new int[26];
        // ramsonNote 的长度大于magazine的长度，直接返回false
        if(ransomNote.length() > magazine.length()){
            return false;
        }
        // 统计 magazine 中字符的出现次数
        for (int i = 0; i < magazine.length(); i++) {
            hash[magazine.charAt(i) - 'a']++;
        }

        // 检查 ransomNote 中的字符
        for (int i = 0; i < ransomNote.length(); i++) {
            hash[ransomNote.charAt(i) - 'a']--;
            if(hash[ransomNote.charAt(i) - 'a'] < 0){
                return false;
            }
        }
        // 返回结果
        return true;
    }
}

参考链接

383.赎金信