383. 赎金信
题目描述
输入两个字符串 ransomNote 和 magazine。
判断能否只用 magazine 中的字母拼出 ransomNote。magazine 里每个字母最多只能用一次。
能拼出返回 true，否则返回 false。
示例 1
输入：ransomNote = "a", magazine = "b" 输出：false
解释：magazine 中没有字母 a。
示例 2
输入：ransomNote = "aa", magazine = "ab" 输出：false
解释：需要两个 a，magazine 只有一个。
示例 3
输入：ransomNote = "aa", magazine = "aab" 输出：true
解释：magazine 正好有两个 a。
数据范围
1 <= ransomNote.length, magazine.length <= 10^5- 两个字符串都只含小写英文字母
解题思路
用长度为 26 的数组 cnt 记下 magazine 里每个字母有多少个，就是“库存”。再遍历 ransomNote，每用一个字母就把对应库存减 1，一旦减到负数就说明不够用，返回 false；全部用完都没有变负就返回 true。
为什么正确
处理完 ransomNote 的前 i 个字符后，cnt[c] = magazine 中 c 的个数 − 前 i 个字符中 c 的个数。
复杂度分析
时间 O(m + n)；空间 O(26)。
易错点
只用 set 判断“字母是否出现”会忽略数量，把 "aa" / "ab" 误判为 true。每次用 str.replace 删字符则是 O(m · n)。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
cnt = [0] * 26
for c in magazine:
cnt[ord(c) - 97] += 1
for c in ransomNote:
cnt[ord(c) - 97] -= 1
if cnt[ord(c) - 97] < 0:
return False
return Trueclass Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] cnt = new int[26];
for (char c : magazine.toCharArray()) {
cnt[c - 'a'] += 1;
}
for (char c : ransomNote.toCharArray()) {
cnt[c - 'a'] -= 1;
if (cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
}class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> cnt(26, 0);
for (char c : magazine) {
cnt[c - 'a'] += 1;
}
for (char c : ransomNote) {
cnt[c - 'a'] -= 1;
if (cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
};func canConstruct(ransomNote string, magazine string) bool {
cnt := make([]int, 26)
for i := 0; i < len(magazine); i++ {
cnt[magazine[i]-'a'] += 1
}
for i := 0; i < len(ransomNote); i++ {
c := ransomNote[i] - 'a'
cnt[c] -= 1
if cnt[c] < 0 {
return false
}
}
return true
}var canConstruct = function(ransomNote, magazine) {
const cnt = new Array(26).fill(0);
for (const c of magazine) {
cnt[c.charCodeAt(0) - 97] += 1;
}
for (const c of ransomNote) {
cnt[c.charCodeAt(0) - 97] -= 1;
if (cnt[c.charCodeAt(0) - 97] < 0) {
return false;
}
}
return true;
};function canConstruct(ransomNote: string, magazine: string): boolean {
const cnt: number[] = new Array(26).fill(0);
for (const c of magazine) {
cnt[c.charCodeAt(0) - 97] += 1;
}
for (const c of ransomNote) {
cnt[c.charCodeAt(0) - 97] -= 1;
if (cnt[c.charCodeAt(0) - 97] < 0) {
return false;
}
}
return true;
}