[LeetCode解題攻略] 49. Group Anagrams

題目描述

給定一個字串陣列 strs，請將字母相同但排列順序不同的單字（即異位詞，Anagrams）分組。可以以任意順序返回結果。

範例

輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

輸入: strs = [""]
輸出: [[""]]

範例 3：

輸入: strs = ["a"]
輸出: [["a"]]

限制條件

• 1 ≤ strs.length ≤ 10^4
• 0 ≤ strs[i].length ≤ 100
• strs[i] 只包含小寫英文字母

解題思路

異位詞（Anagrams）是指由相同字母組成，但字母排列順序不同的單字。因此，所有異位詞的特徵就是它們的字母組合相同。

解法的核心思路是：

• 找出相同特徵的字串，並將它們歸類到同一組。
• 這裡的「特徵」可以使用：
• 1. 排序後的字串（"eat" → "aet"）
  2. 字母計數（頻率表）（"eat" → {e:1, a:1, t:1}）

解法一：排序字串作為 Key（Hash Table）

思路：

1. 對每個字串進行排序，異位詞排序後會變成相同的字串。
2. 使用雜湊表（defaultdict）存儲這些異位詞，Key 為排序後的字串，Value 為原始字串的列表。
3. 回傳雜湊表的所有值。

程式碼：

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        
        for s in strs:
            sorted_str = "".join(sorted(s))  # 排序字母後轉回字串
            anagrams[sorted_str].append(s)   # 加入對應的群組
        
        return list(anagrams.values())  # 取出所有群組

時間與空間複雜度分析

• 時間複雜度：O(n⋅klog⁡k)
• • 其中 n 為 strs 的長度，k 為字串平均長度。
  • 每個字串排序需要 O(klog⁡k) 時間，因此總共為 O(n⋅klog⁡k)。
• 空間複雜度：O(n⋅k)
• • 哈希表存儲了 n 個字串，每個字串長度為 k，因此為 O(n⋅k)。

解法二：字母頻率計數作為 Key（Hash Table）

思路：

1. 使用字母頻率計數來當作 Key，而非排序字串。
2. 每個字串可以轉換為一個 tuple（長度 26，代表 a~z 的出現次數）。
3. 相同的頻率分布代表相同的異位詞，用雜湊表存儲這些群組。

程式碼：

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        
        for s in strs:
            count = [0] * 26  # 建立 26 個字母頻率陣列
            for char in s:
                count[ord(char) - ord('a')] += 1  # 計算每個字母出現次數
            anagrams[tuple(count)].append(s)  # 轉換為 tuple 作為 key
        
        return list(anagrams.values())  # 取出所有群組

時間與空間複雜度分析

• 時間複雜度：O(n⋅k)
• • 計算每個字串的字母頻率需要 O(k) 時間，總共 O(n⋅k)。
  • 比解法一更快，因為不需要排序（省去 O(klog⁡k)）。
• 空間複雜度：O(n⋅k)
• • 需要存儲 n 個字串，且 tuple(count) 佔用 O(26)，所以為 O(n⋅k)。

解法三：使用 Counter（Python 內建函式）

Python 的 collections.Counter 可以直接計算字母頻率，類似於解法二。

程式碼：

from collections import defaultdict, Counter
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        
        for s in strs:
            anagrams[frozenset(Counter(s).items())].append(s)  # 使用 frozenset 作為 key
        
        return list(anagrams.values())

時間與空間複雜度分析

• 時間複雜度：O(n⋅k)
• • Counter(s) 需要 O(k)，總共 O(n⋅k)。
• 空間複雜度：O(n⋅k)
• • Counter(s).items() 轉換為 frozenset 佔用額外空間。

結論

• 如果你想要簡單易懂的方式，推薦解法一（排序字串作為 Key）。
• 如果你想提高效率，推薦解法二（字母頻率計數作為 Key），因為避免了排序 O(klog⁡k) 的開銷。
• 如果你想用 Python 內建函式，解法三（Counter）也是不錯的選擇。

這題使用了雜湊表與字串處理，熟悉後可以應用在很多字串相關的題目上！