力扣经典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)); } }
示例演示
展示了三个不同的示例测试，验证了 ransomNote 是否能由 magazine 中的字符构成的功能。
复杂度分析
该解法的时间复杂度为 O(m + n)，其中 m 是 ransomNote 的长度，n 是 magazine 的长度。空间复杂度为 O(n)，用于存储 magazine 中每个字符的出现次数。
总结
本篇博客介绍了如何判断 ransomNote 是否能由 magazine 中的字符构成。通过使用哈希表记录字符出现次数，并逐个检查 ransomNote 中的字符是否满足条件，最终实现了判断功能。
