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

力扣经典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 中的剩余次数。

具体步骤如下：

1. 使用哈希表 magazineCount 统计 magazine 中每个字符出现的次数。
2. 遍历 ransomNote 中的每个字符，查看是否在 magazineCount 中，并且对应字符的剩余次数大于 0。
3. 如果所有字符都满足条件，则返回 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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

示例演示

展示了三个不同的示例测试，验证了 ransomNote 是否能由 magazine 中的字符构成的功能。

复杂度分析

该解法的时间复杂度为 O(m + n)，其中 m 是 ransomNote 的长度，n 是 magazine 的长度。空间复杂度为 O(n)，用于存储 magazine 中每个字符的出现次数。

总结

本篇博客介绍了如何判断 ransomNote 是否能由 magazine 中的字符构成。通过使用哈希表记录字符出现次数，并逐个检查 ransomNote 中的字符是否满足条件，最终实现了判断功能。