前言

最近在刷 LeetCode，今天要來跟大家分享一下我解「383. Ransom Note」的過程！這題雖然標示為 Easy，解題邏輯不難，但因為對語法不熟，還是讓我卡了一下，所以想把我的解題過程記錄下來，方便未來複習檢視，也給跟我一樣正在學習的朋友們一個參考。如果大神路過有更好的建議幫助我進步歡迎在下方留言。

題目

簡單來說，就是給你兩個字串，一個是「ransomNote」（贖金信），另一個是「magazine」（雜誌）。題目要我們判斷，ransomNote 裡面的每個字母，能不能從 magazine 裡面找到對應的字母，而且每個字母只能用一次。

解題思路

一開始，我想到幾個簡單的判斷條件：

1. 字數檢查： ransomNote 的字數不能比 magazine 多，不然一定組不出來。
2. 字母種類檢查： ransomNote 裡面的字母，一定要是 magazine 裡面的子集。
3. 建立字母頻率表： 使用一個 dictionary 來記錄 magazine 裡面每個字母出現的次數。
4. 逐一檢查 ransomNote： 對於 ransomNote 中的每個字母，檢查 dictionary 裡對應的字母數量是否足夠。

解法

class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    # 檢查字數和字母種類
    if len(ransomNote) > len(magazine) or not set(ransomNote).issubset(set(magazine)):
      return False

    # 建立字母頻率表
    magz_table = dict()
    for m in magazine:
      magz_table[m] = magz_table.get(m, 0) + 1

    # 逐一檢查 ransomNote
    for r in ransomNote:
      if r not in magz_table or magz_table[r] == 0:
        return False
      else:
        magz_table[r] -= 1
    return True

時間複雜度：O(n + m)
空間複雜度：O(n + m)

優化可能性:

我們可以使用 Python 的 collections.Counter 來取代手動建構 hash table。

註:

• Counter 是 collections 模組中的一個子類，用於計數可哈希對象（通常是字符或單詞）。
  功能：Counter 主要用於統計元素的頻率。它會為每個元素創建一個 dictionary 鍵，元素的計數作為 dictionary 的值。
  默認值：如果查詢一個不存在的鍵，Counter 會返回 0，而不是拋出 KeyError。
• dict 是 Python 內置的 hash table，用於存儲任意的鍵值對。
  功能：dict 可以存儲任意類型的鍵值對，而不僅限於計數。
  默認值：如果查詢一個不存在的鍵，dict 會拋出 KeyError，除非使用 dict.get(key, default) 方法。
  靈活性：dict 更加通用，可以存儲各種類型的值，不僅限於計數。

另外，可以去掉 subset 檢查部分，因為這與構建 hash table 相比並不提供顯著的優勢，直接在遍歷 ransomNote 時做檢查即可。

from collections import Counter

class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    # 檢查字數是否足夠
    if len(ransomNote) > len(magazine):
      return False

    # 建立字母頻率表
    magz_counter = Counter(magazine)

    # 逐一檢查 ransomNote
    for char in ransomNote:
      if magz_counter[char] == 0:
        return False
      magz_counter[char] -= 1

    return True

時間複雜度：O(n + m)
空間複雜度：O(n)

Time and Space complexity analysis

Time

1. 長度檢查和集合子集檢查：
   len(ransomNote) > len(magazine) 需要 O(1) 時間。
   set(ransomNote) 和 set(magazine) 的創建時間都是 O(n) 和 O(m)，其中 n 是 ransomNote 的長度，m 是 magazine 的長度。
   set(ransomNote).issubset(set(magazine)) 的檢查時間是 O(n)，因為子集檢查在最壞情況下需要遍歷 ransomNote 中的每個字符。
   綜上，這部分的時間複雜度是 O(n + m)。

2. 構建 magz_table：
   遍歷 magazine 需要 O(m) 時間，每個字符的插入或更新操作在 hash table 中是 O(1) 時間。
   因此，這部分的時間複雜度是 O(m)。

3. 檢查並更新 magz_table：

遍歷 ransomNote 需要 O(n) 時間，每個字符的查找和更新操作在 hash table 中是 O(1) 時間。
因此，這部分的時間複雜度是 O(n)。

綜合來看，總的時間複雜度是 O(n + m)。

Space

1. 集合創建：

set(ransomNote) 和 set(magazine) 各自需要 O(n) 和 O(m) 的空間。
hash table magz_table 最多包含 magazine 中所有不同字符的數量，最壞情況下需要 O(m) 的空間。
如果另外用 counter 創建 ransom_note_count 的 hash table 最壞情況下需要 O(n) 的空間。

綜合來看，總的空間複雜度是 O(n + m)。

卡住的地方

在寫程式的時候，我卡在了一個小細節：

print(set(ransomNote)) # Output: {'a'}
print(set(magazine))  # Output: {'a', 'b'}
print(set(ransomNote) not in set(magazine)) # Output: True

我原本以為 set(ransomNote) not in set(magazine) 可以判斷 ransomNote 的字母是不是 magazine 的子集，但
後來我才發現，not in 因為它的意思是檢查 set(ransomNote) 是否作為一個整體元素存在於 set(magazine) 中，而不是判斷一個集合是不是另一個集合的子集。正確的做法應該是使用 issubset()。

Example

假設 ransomNote 為 "aa"，magazine 為 "aab"：

• set(ransomNote) 是 {'a'}。
• set(magazine) 是 {'a', 'b'}。

使用 issubset 方法：

set(ransomNote).issubset(set(magazine)) # True

使用 not in 方法：

set(ransomNote) not in set(magazine) # True

前者是正確的，因為它檢查 'a' 是否在 {'a', 'b'} 中。而後者是不正確的，因為 {'a'} 不是 {'a', 'b'} 的一個元素。

Lesson learn

這題幫我

1. 加強創建 hash table 的用法（Python 的 set 和 dict 都是基於 hash table 實現的）

• set：用來存儲不重複的元素，主要用於檢查唯一性和集合操作（如聯集、交集和差集）。
• dict：用來存儲鍵值對（key-value pairs），主要用於快速查找、插入和刪除鍵值對。

2. set, dict, collect 的語法熟悉度

列出幾個適合使用 hash table 的情況:

1. 頻率計數：

當需要計算元素出現的次數時，例如字符、單詞、或數字的頻率。
例子：統計字符串中每個字符的出現次數，檢查兩個字符串是否為字母異位詞（Anagram）。

2. 快速查找：

當需要快速查找某個元素是否存在時。
例子：從一個列表中快速查找某個值，或在 dictionary 中查找某個鍵是否存在。

3. 唯一性檢查：

當需要檢查元素是否唯一時。
例子：檢查一個字符串中的字符是否全都唯一，檢查一組數字中是否有重複值。

4. 配對與對應：

當需要建立一對一對應或一對多對應的關係時。
例子：將每個單詞映射到其定義，或將學生 ID 映射到學生信息。

5. 累積求和或其他操作：

當需要累積計算某些數據時，例如求和、計算最大值或最小值。
例子：累積計算不同產品的銷售額，統計每個類別的商品數量。