力扣经典150题第三十九题：赎金信

用户8589624

发布于 2025-11-13 16:03:28

210

文章被收录于专栏：nginxnginx

力扣经典150题第三十九题：赎金信

引言

本篇博客介绍了力扣经典150题中的第三十九题：赎金信。题目要求判断字符串 ransomNote 是否能由字符串 magazine 中的字符构成，且 magazine 中的每个字符只能使用一次。

题目详解

给定两个字符串 ransomNote 和 magazine，要求判断 ransomNote 是否能由 magazine 中的字符构成。具体要求如下：

magazine 中的每个字符只能在 ransomNote 中使用一次。
如果能够构成，则返回 true；否则返回 false。示例 1：

输入：ransomNote = “a”, magazine = “b” 输出：false 示例 2：

输入：ransomNote = “aa”, magazine = “ab” 输出：false 示例 3：

输入：ransomNote = “aa”, magazine = “aab” 输出：true

解题思路

为了判断 ransomNote 是否能由 magazine 中的字符构成，可以利用哈希表记录 magazine 中每个字符的出现次数，然后逐个检查 ransomNote 中的字符是否可以在哈希表中找到并且次数不超过 magazine 中的剩余次数。

具体步骤如下：

使用哈希表 magazineCount 统计 magazine 中每个字符出现的次数。
遍历 ransomNote 中的每个字符，查看是否在 magazineCount 中，并且对应字符的剩余次数大于 0。
如果所有字符都满足条件，则返回 true；否则返回 false。

通过上述步骤，可以判断 ransomNote 是否能由 magazine 中的字符构成。

代码实现

import java.util.HashMap;
import java.util.Map;

public class RansomNote {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }

        // 哈希表记录 magazine 中每个字符的出现次数
        Map<Character, Integer> magazineCount = new HashMap<>();
        for (char ch : magazine.toCharArray()) {
            magazineCount.put(ch, magazineCount.getOrDefault(ch, 0) + 1);
        }

        // 检查 ransomNote 中的字符是否能够由 magazine 构成
        for (char ch : ransomNote.toCharArray()) {
            if (!magazineCount.containsKey(ch) || magazineCount.get(ch) <= 0) {
                return false;
            }
            magazineCount.put(ch, magazineCount.get(ch) - 1);
        }

        return true;
    }

    public static void main(String[] args) {
        RansomNote solution = new RansomNote();

        // 示例测试
        String ransomNote1 = "a";
        String magazine1 = "b";
        System.out.println("ransomNote: " + ransomNote1 + ", magazine: " + magazine1);
        System.out.println("结果: " + solution.canConstruct(ransomNote1, magazine1));

        String ransomNote2 = "aa";
        String magazine2 = "ab";
        System.out.println("ransomNote: " + ransomNote2 + ", magazine: " + magazine2);
        System.out.println("结果: " + solution.canConstruct(ransomNote2, magazine2));

        String ransomNote3 = "aa";
        String magazine3 = "aab";
        System.out.println("ransomNote: " + ransomNote3 + ", magazine: " + magazine3);
        System.out.println("结果: " + solution.canConstruct(ransomNote3, magazine3));
    }
}