# Ransom Note

###### tags: `Easy`
> [name=出題者 : 曾致銘]

## Problem
給定兩個字串 `ransomNote` 跟 `magazine`，倘若 `ransomNote` 裡的所有字元皆可用 `magazine` 裡的字元組成則印出 `true` ，反之印出 `false`。注意到每一個 `magazine` 的字元皆只能使用一次。

### Examples
範例 1：

輸入: a b
輸出: false
解釋: magazine 裡沒有 'a'

範例 2：

輸入: aa ab
輸出: false
解釋: magazine 裡雖有 'a', 但數量不足

範例 3：

輸入: aa aab
輸出: true
解釋: magazine 裡有數量足夠的 'a'

### Constraints
- $1 \le$ `ransomNote.size(), magazine.size()` $\le 10^5$
- `ransomNote` 跟 `magazine` 只含小寫英文字母。

### Hints

## Solution
:::spoiler Description
### Approach 1: 統計字元數量

#### 思路
題目要求使用字串 `magazine` 中的字元來組成 `ransomNote`，且 `magazine` 中的每個字元只能使用一次，那麼我們只需要統計所有在 `magazine` 跟 `ransomNote` 裡的各個英文字母數量，判斷 `magazine` 裡的每個字母數量是否皆大於等於 `ransomNote` 裡該字母的數量即可。

#### 算法
1. 判斷如果 `magazine` 的長度小於 `ransomNote`，印出 `false`。
2. 創建一長度為 26 的整數陣列 `cnt`，儲存各個字母在 `magazine` 中的數量。
3. 統計 `magazine` 中從字母 a 開始計算的第 `i` 個字母的數量入 `cnt[i]`，其中 $0 \le$ `i` $< 26$。
4. 遍歷 `ransomNote` 中的每個字母，並把對應的 `cnt[i]` 值減去 1 作為使用的紀錄。
5. 判斷如果 `cnt[i]` 小於 0 (不夠用)，印出 `false`。
6. 重複步驟 4, 步驟 5。
7. 遍歷結束後，印出 `true`。

// 以下省略 cin，僅呈現演算法及輸出部分
// 步驟 1
if (ransomNote.size() > magazine.size()) {
    cout << "false";
    return 0;
}

// 步驟 2
int cnt[26] = {};

for (auto c : magazine) {
    // 步驟 3
    cnt[c - 'a']++;
}

for (auto c : ransomNote) {
    // 步驟 4
    cnt[c - 'a']--;
    // 步驟 5
    if (cnt[c - 'a'] < 0) {
        cout << "false";
        return 0;
    }
}

// 步驟 7
cout << "true";

#### 複雜度分析
- 時間複雜度: $O(m+n)$ 其中 $m$ 為 `ransomNote`，$n$ 為 `magazine` 的長度。因為我們只使用了兩個單層迴圈。
- 空間複雜度: $O(\vert S \vert)$ 其中 $S$ 是字元集合，由於本題限定只有小寫英文字母，故 $\vert S \vert = 26$。

### 完整解答

#include <iostream>
using namespace std;

int main() {
    string ransomNote, magazine;
    cin >> ransomNote >> magazine;
    if (ransomNote.size() > magazine.size()) {
        cout << "false" << endl;
        return 0;
    }
    
    int cnt[26] = {};
    
    for (auto c : magazine) {
        cnt[c - 'a']++;
    }
    
    for (auto c : ransomNote) {
        cnt[c - 'a']--;
        if (cnt[c - 'a'] < 0) {
            cout << "false" << endl;
            return 0;
        }
    }
    
    cout << "true" << endl;
}

:::

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