赎金信
# 📃 题目描述
题目链接:383. 赎金信 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。
(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次)
示例 1:
输入:ransomNote = "a", magazine = "b"
输出:false
示例 2:
输入:ransomNote = "aa", magazine = "ab"
输出:false
示例 3:
输入:ransomNote = "aa", magazine = "aab"
输出:true
提示:
你可以假设两个字符串均只含有小写字母。
# 🔔 解题思路
这题好办,对于快速找字符找数字这种题目,我们应该迅速想到哈希表。
利用一个 map 处理 magazine,key 存储字符,value 存储该字符出现的次数
然后遍历 ransomNote,若某个字符串存在于 map 中,则对应的 value - 1,在减 1 之前,如果 value 已经等于 0 了,意思就是说 magazine 中这个字符的数量已经不足以供 ransomNote 使用了,则立即返回 false;或者,ransomNote 的某个字符串不存在于 map 中,立即返回 false。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (magazine == null || magazine.length() == 0) {
return true;
}
else if (ransomNote == null || ransomNote.length() == 0) {
return false;
}
Map<Character, Integer> map = new HashMap<>();
// 利用 map 处理 magazine,key 存储字符,value 存储该字符出现的次数
for (char ch : magazine.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// 遍历 ransomNote
for (char ch : ransomNote.toCharArray()) {
// ransomNote 的某个字符串不存在于 map 中,立即返回 false
if (!map.containsKey(ch)) {
return false;
}
// 在减 1 之前,如果 value 已经等于 0 了,则立即返回 false
if (map.get(ch) == 0) {
return false;
}
map.put(ch, map.get(ch) - 1);
}
return true;
}
}
和 242. 有效的字母异位词 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 一样,对于哈希表中的 key,如果哈希值比较连续且固定,我们可以用数组的下标来等同。这个题目中的 key 存储的就是 26 个字母,那我们只需要将其转成 int 作为数组的下标即可:
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (magazine == null || magazine.length() == 0) {
return true;
}
else if (ransomNote == null || ransomNote.length() == 0) {
return false;
}
int[] nums = new int[26];
// 利用 map 处理 magazine,key 存储字符,value 存储该字符出现的次数
for (char ch : magazine.toCharArray()) {
nums[ch - 'a'] += 1;
}
// 遍历 ransomNote
for (char ch : ransomNote.toCharArray()) {
// ransomNote 的某个字符串不存在于 map 中,立即返回 false
// 在减 1 之前,如果 value 已经等于 0 了,则立即返回 false
if (nums[ch - 'a'] == 0) {
return false;
}
nums[ch - 'a'] -= 1;
}
return true;
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~