題目說明

題號：383.Ransom Note

給定兩個字串 ransomNote 和 magazine，判斷是否可以用 magazine 裡的字母組成 ransomNote。

• 每個字母在 magazine 裡只能用一次。

範例

Input: ransomNote = "a", magazine = "b"
Output: false

Input: ransomNote = "aa", magazine = "ab"
Output: false

Input: ransomNote = "aa", magazine = "aab"
Output: true

解法思路（Hash Map / 計數法）

1. 遍歷 magazine，統計每個字母出現的次數。

2. 遍歷 ransomNote，檢查對應字母是否足夠：

   • 沒有這個字母 → 回傳 false。
   • 次數為 0 → 回傳 false。
   • 否則消耗掉一次字母數量。

3. 如果整個檢查都能完成 → 回傳 true。

複雜度分析

時間複雜度：O(n + m)
空間複雜度：O(1)（字母只有 26 種，最多存 26 個 key）

程式碼

Java 解法

import java.util.HashMap;

public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> count = new HashMap<>();

    for (char c : magazine.toCharArray()) {
        count.put(c, count.getOrDefault(c, 0) + 1);
    }
    
    for (char c : ransomNote.toCharArray()) {
        if (!count.containsKey(c) || count.get(c) == 0) {
            return false;
        }
        count.put(c, count.get(c) - 1);
    }
    
    return true;
}

}

Python 解法

def canConstruct(ransomNote, magazine):
count = {}

for c in magazine:
    count[c] = count.get(c, 0) + 1

for c in ransomNote:
    if c not in count or count[c] == 0:
        return False
    count[c] -= 1

return True

Trace 範例

輸入：

ransomNote = "aa"
magazine = "aab"

1. 先統計 magazine：

   • 'a' → {'a': 1}
   • 'a' → {'a': 2}
   • 'b' → {'a': 2, 'b': 1}

結果：

count = { 'a': 2, 'b': 1 }

2. 檢查 ransomNote：

   • 第一個 'a' → OK，用掉一個 → {'a': 1, 'b': 1}
   • 第二個 'a' → OK，用掉一個 → {'a': 0, 'b': 1}

3. 檢查完畢 → 所有字母都有 → 回傳 true ✅

Java 與 Python 的差異

Java 必須宣告 HashMap <Character, Integer>，寫法比較嚴謹，要用 getOrDefault()、containsKey() 來處理不存在的情況。
Python 則簡單很多，字典 dict 搭配 get()預設值就能快速處理，不需要額外判斷，程式碼更精簡。

心得

這題讓我更清楚看到 哈希表（Hash Map / dict）的威力。
一開始我想用巢狀迴圈去找 ransomNote 的每個字母，但這樣時間複雜度會變成 O(n*m)，效率很差。改用哈希表後，可以先把 magazine 字母的數量統計好，接著在檢查 ransomNote 的時候，就能直接用 O(1) 的時間確認是否足夠。
想像成「先記錄資源，再消耗資源」，比一邊找一邊消耗要有效率很多。