題目連結(https://leetcode.com/problems/ransom-note/description/?envType=study-plan-v2&envId=top-interview-150)

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

多練習 Hash map 題目，蠻多字串題會用到

1. Repeat（題目重複確認）

• 輸入：兩個字串 ransomNote 和 magazine
• 輸出：true 如果 ransomNote 中的每個字元都可以由 magazine 組成
• 前提：
  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.

2. Examples（舉例確認理解）

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

3. Approach（解題思路）

方法 ：hash map

• 使用 hash map 統計字母出現次數
• 時間複雜度: O(m + n) 需要遍歷兩個字串
• 空間複雜度: O(1) - 最多26個字母

4. Code（C++）

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mp;
        // 統計 magazine 中每個字母的數量
        for (char c : magazine) {
            mp[c]++;
        }
        // 檢查 ransomNote 中每個字母
        for(char c : ransomNote){
            if(mp[c] == 0) return false;
            mp[c]--;
        }
        return true;
    }
};

5. Test 範例

略

6. 相關題目與延伸概念

691. Stickers to Spell Word

1160. Find Words That Can Be Formed by Characters

7. 補充：語法＆注意事項

遍歷字串中每個字母，出現後進行 mp[c]++ 表示出現次數加一，記錄各字母出現次數，再讓 ransomNote 遍歷時減掉字母次數，如果有遇到等於 0 的字母，表示 ransomNote 多出現了不該出現，也就是 magazine 沒有的字母，不符題目規則。

for (char c : magazine) {
            mp[c]++;
        }

時間與空間的改進：

• 這個解法利用了哈希表的快速查找特性，確保每個字母的檢查時間為常數時間比陣列解法來的快。

ps. 部分內容經 AI 協助整理