383. Ransom Note (贖金信)

英文版點我｜中文版點我

↑看個小廣告，支持好內容↑

❶ Hash Table (索引、桶子)

題意不複雜，判斷給定的 magazine 字庫能否湊成 ransomNote 就行，這是蠻直觀的計數問題：

1. 計算字庫 (magazine) 裡各種字母的數量
2. 逐一扣除 ransomNote 含有的字母

要是過程中扣出負值，就代表有字母不夠用了，反之則為成功。由於小寫字母共 26 種，我們用 map 或是長度 26 的陣列來統計都 OK！空間複雜度可以視為 O(26)。

但如果我們不想花耗任何空間，是有可能的嗎？

❷ Replace

那我們就得模擬 ransomNote 的產生了，這邊有個實例：

// magazine="apple", ransomNote="panel"

1. 字庫找到 a，拿掉目標字的 a 代表已經湊得：p_nel。
2. 字庫找到 p，拿掉目標字的 p 代表已經湊得：__nel。
3. 字庫找到 p，目標字已沒有 p 因此無影響。​
4. 字庫找到 l，拿掉目標字的 l 代表已經湊得：__ne_。
5. 字庫找到 e，拿掉目標字的 e 代表已經湊得​：__n__。​(n 沒被湊出，任務失敗)

對於字庫出現的字母，我們一一拿去取代目標單字，倘若 ransomNote 變成空字串，即表示單字有成功組成。這個方法省去計數器的空間，卻需要反覆遍歷字串執行 replace，可以說是用時間換取了空間。

• 本題分類標籤：Hash Table、String、Counting
• 本題正解率＝60.5％

❤️ 若內容對你實用，歡迎追蹤本專題，或小額贊助支持～
⭐ 這是我的第 20 篇刷題筆記，完整解題索引看這裡 → Here