383. Ransom Note

📘 題目敘述

給定兩個字串 ransomNote 與 magazine，如果 ransomNote 可以由 magazine 中的字母構成，則回傳 true，否則回傳 false。

magazine 中的每個字母只能使用一次（也就是每個字元最多被拿來用一次）。

條件限制

• 1 ≤ ransomNote.length, magazine.length ≤ 10^5
• ransomNote 與 magazine 只包含小寫英文字母

🧠 解題思路

我在看這題時，是把問題想成一個「逐字配對」的過程。

我有一個需要完成的字串 ransomNote，以及一個可以使用的字串 magazine，我要確認的是：能不能依序替 ransomNote 中的每一個字母，在 magazine 中找到一個可以用、而且不會重複使用的對應字母。

因此我先設定一個布林變數 same，用來表示目前的判斷結果：

• same = true：到目前為止，每一個需要的字母都成功找到
• same = false：已經出現至少一個無法構成的字母

接下來，我依序處理 ransomNote 中的每一個字母，對於目前的字母 ransomNote[i]，會出現以下幾種情況：

情況一：在 magazine 中找到相同字母

• 表示這個字母可以被成功構成
• 因為每個字母只能使用一次，找到後會將該字母從 magazine 中刪除
• 接著繼續處理下一個 ransomNote 字母

情況二：整個 magazine 都找不到相同字母

• 代表目前的 ransomNote[i] 無法被構成
• 此時將 same 設為 false
• 表示答案已經不成立

情況三：magazine 已經沒有任何字母

• 如果在處理過程中發現 magazine 已經為空
• 後續不可能再提供任何字母
• 因此也需要將 same 設為 false

整個流程結束後，只需要回傳 same：

• 若為 true，代表所有字母皆成功配對
• 若為 false，代表至少有一個字母無法構成

💻 程式碼實作（第一直覺解）

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        bool same = true;
        for (int i = 0; i < ransomNote.size(); i++) {
            if (magazine.size() == 0) {
                same = false;
            }
            for (int j = 0; j < magazine.size(); j++) {
                if (ransomNote[i] == magazine[j]) {
                    magazine.erase(j, 1);
                    break;
                } else {
                    if (j == magazine.size() - 1) {
                        same = false;
                    }
                }
            }
        }
        return same;
    }
};

🔗 題目連結

https://leetcode.com/problems/ransom-note/