題目描述:給定兩個字串 ransomNote 和 magazine,判斷 ransomNote 能否由 magazine 中的字母構成。每個字母只能使用一次。
解題思路:統計 magazine 中每個字母的頻率,存入長度 26 的陣列。再遍歷 ransomNote,對每個字母減少計數;若任何字母計數降至負數,表示 magazine 中該字母不夠用,回傳 false。否則回傳 true。
時間複雜度:O(m + n) — m 為 magazine 長度,n 為 ransomNote 長度,各遍歷一次。
空間複雜度:O(1) — 固定大小的 26 個字母計數陣列。
1. Initialize count[26] = {0}
2. For each char c in magazine: count[c - 'a']++
3. For each char c in ransomNote:
a. Decrement count[c - 'a']
b. If count[c - 'a'] < 0, return false
4. Return true雜湊表 O(m + n):用 unordered_map<char, int> 取代固定陣列 — 功能相同,但在僅含小寫字母時陣列更快。
排序 O((m + n) log(m + n)):排序兩個字串後用雙指標比對 — 邏輯直觀,但時間複雜度較差。
magazine 是串流資料(不能預讀全部),解法如何改變?