Ransom Note

February 11, 2025•--

Check if ransom note can be constructed from magazine using Hash Map

Determine if a ransom note can be constructed from magazine letters

問題描述

給你兩個字串：ransomNote 和 magazine，判斷 ransomNote 能不能由 magazine 裡面的字符構成。

如果可以，返回 true；否則返回 false。

magazine 中的每個字符只能在 ransomNote 中使用一次。

範例

輸入：ransomNote = "a", magazine = "b"
輸出：false

輸入：ransomNote = "aa", magazine = "ab"
輸出：false

輸入：ransomNote = "aa", magazine = "aab"
輸出：true

限制條件

1 <= ransomNote.length, magazine.length <= 10⁵
ransomNote 和 magazine 由小寫英文字母組成

解題思路

### 計數 magazine 的字符統計 magazine 中每個字符出現的次數

檢查 ransomNote 的需求遍歷 `ransomNote`，檢查每個字符是否在 `magazine`

中有足夠的數量

### 扣除已使用的字符每使用一個字符，就從計數中扣除，避免重複使用

解決方案

typescript

export function canConstruct(ransomNote: string, magazine: string): boolean {
  const charCount = new Map<string, number>();
 
// 統計 magazine 中每個字符的出現次數
for (const char of magazine) {
charCount.set(char, (charCount.get(char) || 0) + 1);
}
 
// 檢查 ransomNote 中的每個字符
for (const char of ransomNote) {
const count = charCount.get(char) || 0;
if (count === 0) {
return false; // 字符不足或不存在
}
charCount.set(char, count - 1); // 扣除已使用的字符
}
 
return true;
}