383. Ransom Note

題目 / Problem

中文： 給定兩個字串 ransomNote（勒索信）和 magazine（雜誌）。如果 ransomNote 裡的每一個字母都可以從 magazine 裡「剪」出來拼湊而成，就回傳 true，否則回傳 false。注意：magazine 裡的每個字母只能用一次。換句話說，對於每一個字母，ransomNote 需要的數量不能超過 magazine 擁有的數量。

English: You are given two strings, ransomNote and magazine. Return true if ransomNote can be built entirely from the letters available in magazine, otherwise return false. Each letter in magazine may be used at most once. In plain terms: for every letter, the count you need in ransomNote must not exceed the count you have in magazine.

約束 / Constraints: - 1 <= ransomNote.length, magazine.length <= 10^5 - 兩個字串都只由小寫英文字母組成 / both strings consist only of lowercase English letters.

範例 / Worked example: - ransomNote = "aa", magazine = "aab" → true，因為 magazine 有兩個 a，剛好夠拼出 "aa"。/ magazine has two as, exactly enough to spell "aa".

名詞解釋 / Glossary

• 計數陣列 / Counting array (frequency array)： 一個固定大小的陣列，用每個位置（index）代表一個字母，陣列裡存的數字就是「這個字母出現了幾次」。因為只有 26 個小寫字母，我們用一個長度 26 的整數陣列即可。A fixed-size array where each index stands for one letter and the stored value is how many times that letter appears. With only 26 lowercase letters, a length-26 int array is enough.
• 雜湊表 / Hash map： 一種「鍵 → 值」的容器，可以用任意鍵（這裡是字元）快速查到對應的值（出現次數）。C++ 的 unordered_map 就是雜湊表。A "key → value" container that lets you look up a value (here, a count) by an arbitrary key (here, a character) in roughly constant time. C++'s unordered_map is a hash map.
• ASCII 值 / ASCII value： 每個字元在電腦裡其實是一個整數。小寫字母 'a' 到 'z' 的整數值是連續的，所以 c - 'a' 會得到 0 到 25 的索引。Each character is internally an integer. Lowercase 'a'–'z' are consecutive, so c - 'a' maps a letter to an index 0–25.
• O(n) 時間複雜度 / O(n) time complexity： 執行時間大致和輸入長度 n 成正比；掃過字串一遍就是 O(n)。Running time grows roughly in proportion to the input length n; scanning the string once is O(n).

思路

最直覺的暴力法是：對於 ransomNote 裡的每一個字母，去 magazine 裡找一個還沒用過的相同字母，找到就把它「劃掉」。這需要對每個字元都掃一遍 magazine，時間複雜度是 O(n × m)，在長度達到 10^5 時太慢，而且還要額外標記哪些字母已被用掉，很麻煩。更聰明的觀察是：我們其實不在乎字母的「位置」，只在乎「數量」。只要 magazine 裡某個字母的數量 ≥ ransomNote 裡需要的數量，就一定拼得出來。因此我們先用一個長度 26 的計數陣列統計 magazine 裡每個字母出現幾次；接著掃 ransomNote，每遇到一個字母就把對應計數減一，如果減之前發現該字母的計數已經是 0，代表雜誌裡不夠用，立刻回傳 false。能掃完整個 ransomNote 都沒出問題，就回傳 true。為什麼用 c - 'a' 當索引？因為字母是連續的整數，這樣能把字元直接對應到 0–25 的格子，查表 O(1)。整個過程只掃兩遍字串，時間 O(n)，空間是固定的 26 格 O(1)。

The brute-force idea is: for each letter in ransomNote, scan magazine for an unused matching letter and cross it off. That costs O(n × m) time and needs bookkeeping to track used letters — too slow at length 10^5. The key insight is that positions don't matter, only counts do. If magazine contains at least as many of each letter as ransomNote needs, the note can always be assembled. So we first tally magazine into a length-26 counting array. Then we walk through ransomNote; for each letter we decrement its count, but if the count is already 0 before decrementing, the magazine has run out of that letter and we return false immediately. If we finish the whole note without running short, we return true. We use c - 'a' as the index because lowercase letters are consecutive integers, giving an O(1) slot lookup. The whole thing scans each string once, so it's O(n) time and O(1) space (a fixed 26 slots).

逐步走查 / Walkthrough

範例 / Example: ransomNote = "aa", magazine = "aab".

Step 1 — 統計 magazine / Tally the magazine. 掃過 "aab"：

統計結果 / Result: a → 2, b → 1。

Step 2 — 掃 ransomNote / Scan the note "aa".

掃完整個 ransomNote 都沒有遇到不足的情況 / finished the note without running short → 回傳 true / return true. ✅

Solution — C

// 演算法 / Algorithm:
// 用長度 26 的計數陣列記錄 magazine 每個字母的數量，
// 再掃 ransomNote 逐一扣減；若某字母不夠用就回傳 false。
// Tally magazine's letters in a 26-slot array, then decrement per
// note letter; return false the moment a letter runs out.

#include <stdbool.h>   // 讓我們能用 bool / true / false / lets us use bool, true, false

bool canConstruct(char* ransomNote, char* magazine) {
    int count[26] = {0};                  // 26 個字母的計數，全部初始化為 0 / counts for 26 letters, all zeroed
                                          // {0} 會把整個陣列填 0 / {0} zero-initializes the whole array

    // 第一遍：統計 magazine 裡每個字母出現幾次 / Pass 1: count each letter in magazine
    for (int i = 0; magazine[i] != ''; i++) {   // C 字串以 '' 結尾，遇到它就停 / C strings end at ''
        count[magazine[i] - 'a']++;       // magazine[i]-'a' 把字母轉成 0..25 的索引 / map letter to index 0..25
    }                                     // ++ 表示該字母數量加一 / ++ adds one to that letter's tally

    // 第二遍：掃 ransomNote，逐一檢查並扣減 / Pass 2: walk the note, check then decrement
    for (int i = 0; ransomNote[i] != ''; i++) {
        int idx = ransomNote[i] - 'a';    // 算出這個字母對應的索引 / index for this needed letter
        if (count[idx] == 0) {            // 已經沒有這個字母可用了 / no copies of this letter left
            return false;                 // 無法拼出，立即回傳 false / can't build it, return false now
        }
        count[idx]--;                     // 用掉一個，數量減一 / consume one copy, decrement
    }

    return true;                          // 全部字母都湊齊了 / every needed letter was available
}

Solution — C++

// 演算法 / Algorithm:
// 用長度 26 的計數陣列統計 magazine 的字母，
// 再掃 ransomNote 逐一扣減；任何字母不夠就回傳 false。
// Tally magazine's letters in a 26-slot array, then decrement per
// note letter; return false as soon as one runs out.

#include <string>
#include <array>
using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // std::array<int,26> 是固定大小陣列，{} 把元素全設為 0
        // std::array<int,26> is a fixed-size array; {} zero-initializes every element
        array<int, 26> count{};

        // range-for：依序取出 magazine 的每個字元 c（char 型別）
        // range-for: iterate over each character c of magazine
        for (char c : magazine) {
            count[c - 'a']++;             // c-'a' 轉成 0..25 索引，該字母計數加一 / map to 0..25, increment
        }

        // 掃 ransomNote，每個字母先檢查再扣減 / scan the note, check before decrementing
        for (char c : ransomNote) {
            int idx = c - 'a';            // 這個字母對應的索引 / index of this needed letter
            if (count[idx] == 0) {        // 沒有剩餘的這個字母 / none of this letter remain
                return false;             // 拼不出來 / cannot construct
            }
            count[idx]--;                 // 用掉一個 / consume one copy
        }

        return true;                      // 所有字母都夠 / all letters were available
    }
};

備註 / Note：這裡用固定陣列而非 unordered_map，因為字母只有 26 種，陣列更快也更省記憶體；若字元種類很多（例如 Unicode），才會改用 unordered_map<char,int> 這種雜湊表。We use a fixed array instead of unordered_map because there are only 26 letters — the array is faster and lighter. A hash map (unordered_map<char,int>) would shine only when the character set is large (e.g. Unicode).

複雜度 / Complexity

• Time: O(n + m) — 其中 n 是 ransomNote 長度，m 是 magazine 長度。我們各掃一遍字串，每次操作（索引計算、加減、比較）都是 O(1)，所以總和與兩字串長度成正比。We scan each string exactly once and every per-character operation is O(1), so total time is proportional to the combined length. 通常簡寫為 O(n) / often written O(n).
• Space: O(1) — 計數陣列固定為 26 格，與輸入長度無關，不會隨 n 變大。The counting array is a fixed 26 slots regardless of input size, so the extra space is constant.

Pitfalls & Edge Cases

• 方向別搞反 / Don't reverse the roles： 是「magazine 提供字母給 ransomNote」。先統計 magazine、再扣 ransomNote，弄反就會得到錯誤答案。Tally magazine and consume against ransomNote, not the other way around.
• 檢查要在扣減「之前」 / Check before you decrement： 如果先 count[idx]-- 再判斷，計數可能變成 -1，邏輯就亂了。先確認 count[idx] != 0 再扣，能保證永不超用。Verify the count is non-zero before decrementing; decrementing first could push it negative and break the logic.
• 索引用 c - 'a' 而非 c 本身 / Use c - 'a', not c： 字元 'a' 的數值是 97，直接拿來當索引會越界。減掉 'a' 才會落在 0–25。'a' is 97; using the raw char as an index goes out of bounds. Subtracting 'a' maps it into 0–25.
• ransomNote 比 magazine 長 / Note longer than magazine： 演算法自然處理——某個字母遲早會不夠，回傳 false，不需要特別判斷長度。Handled automatically: a letter will eventually run short and trigger false; no special length check needed.
• 不會溢位 / No overflow risk： 最大長度 10^5 遠小於 int 上限，計數陣列用 int 完全足夠。Max length 10^5 is far below int's limit, so an int counter is safe.