力扣链接：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
约束:
1 <= ransomNote.length, magazine.length <= 10^5ransomNote和magazine由小写英文字母组成
思路
- 本题等同于求
magazine是否能包含ransomNote中的所有字符。 - 先对
magazine进行统计，得出每个字符对应的字数，结果存储在Map中。每一次都是一个加一的操作。 - 下一步做什么？
点击查看答案
遍历
ransomNote，对当前字符对应的数量进行减一操作（反向操作）。如果某个字符的数量小于0，则返回false。
步骤
先对
magazine进行字符和字数统计，结果存储在Map中。charToCount = new Map() for (character in magazine) { charToCount[character] += 1 }然后，遍历
ransomNote，并对Map中的数据进行反向操作。如果某个字符的字数小于0，则返回false。charToCount = new Map() for (character in magazine) { charToCount[character] += 1 } for (character in ransomNote) { charToCount[character] -= 1 if (charToCount[character] < 0) { return false } } return true
复杂度
时间复杂度
O(N)
空间复杂度
O(N)
Java #
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
var charToCount = new HashMap<Character, Integer>();
for (var character : magazine.toCharArray()) {
charToCount.put(character, charToCount.getOrDefault(character, 0) + 1);
}
for (var character : ransomNote.toCharArray()) {
charToCount.put(character, charToCount.getOrDefault(character, 0) - 1);
if (charToCount.get(character) < 0) {
return false;
}
}
return true;
}
}
Python #
# from collections import defaultdict
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
char_to_count = defaultdict(int)
for char in magazine:
char_to_count[char] += 1
for char in ransomNote:
char_to_count[char] -= 1
if char_to_count[char] < 0:
return False
return True
JavaScript #
var canConstruct = function (ransomNote, magazine) {
const charToCount = new Map()
for (const character of magazine) {
charToCount.set(character, (charToCount.get(character) || 0) + 1)
}
for (const character of ransomNote) {
charToCount.set(character, (charToCount.get(character) || 0) - 1)
if (charToCount.get(character) < 0) {
return false
}
}
return true
};
C# #
public class Solution
{
public bool CanConstruct(string ransomNote, string magazine)
{
var charToCount = new Dictionary<char, int>();
foreach (char character in magazine)
charToCount[character] = charToCount.GetValueOrDefault(character, 0) + 1;
foreach (char character in ransomNote)
{
charToCount[character] = charToCount.GetValueOrDefault(character, 0) - 1;
if (charToCount[character] < 0)
{
return false;
}
}
return true;
}
}
Ruby #
def can_construct(ransom_note, magazine)
char_to_count = Hash.new(0)
magazine.each_char { |c| char_to_count[c] += 1 }
ransom_note.each_char do |c|
char_to_count[c] -= 1
return false if char_to_count[c] < 0
end
true
end
Go #
func canConstruct(ransomNote string, magazine string) bool {
charToCount := make(map[rune]int)
for _, char := range magazine {
charToCount[char]++
}
for _, char := range ransomNote {
charToCount[char]--
if charToCount[char] < 0 {
return false
}
}
return true
}
C++ #
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> char_to_count;
for (char character : magazine) {
char_to_count[character]++;
}
for (char character : ransomNote) {
char_to_count[character]--;
if (char_to_count[character] < 0) {
return false;
}
}
return true;
}
};