陳憲億 Joseph Chen | Software Engineer & AI Developer

5 min read

1.2k views

Group Anagrams 是 Valid Anagram（EP.02）的進階版。上一題只需要判斷兩個字串是不是 anagram，這一題要把一組字串裡所有 anagram 分到同一組。解這題需要同時理解「如何找出 anagram 的共同特徵」和「Python 的 defaultdict 怎麼用」。

題目理解

Input / Output

Input:  strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

說明：eat、tea、ate 是同一組 anagram（用了相同的字母 a, e, t）
     tan、nat 是同一組 anagram（用了相同的字母 a, n, t）
     bat 自成一組

關鍵問題：如何讓 anagram 有相同的 key？

Anagram 的本質：相同的字母，不同的排列順序。所以如果把每個字排序，所有 anagram 排序後都會得到一樣的字串。

排序作為 key 的概念

"eat"  → sorted → ['a', 'e', 't'] → tuple → ('a', 'e', 't')
"tea"  → sorted → ['a', 'e', 't'] → tuple → ('a', 'e', 't')  ✅ 相同
"ate"  → sorted → ['a', 'e', 't'] → tuple → ('a', 'e', 't')  ✅ 相同
"tan"  → sorted → ['a', 'n', 't'] → tuple → ('a', 'n', 't')  ← 不同組
"bat"  → sorted → ['a', 'b', 't'] → tuple → ('a', 'b', 't')  ← 不同組

⚠️ 為什麼不用 str 而用 tuple？
sorted("eat") 回傳的是 list（['a', 'e', 't']），而 list 不能當 dict 的 key（list 是可變的，不能 hash）。
用 tuple(sorted(s)) 轉成 tuple，就可以當 key 了。

defaultdict：不用再寫 if key not in dict

普通 dict 存取不存在的 key 會拋 KeyError。每次要新增一個 key 都要先判斷它存不存在：

普通 dict — 需要手動初始化

# 用普通 dict 分組，每次要先判斷
result = {}
for s in strs:
    key = tuple(sorted(s))
    if key not in result:        # 每次都要檢查
        result[key] = []
    result[key].append(s)

defaultdict 讓你指定「當 key 不存在時，自動建立什麼預設值」，省掉那個 if 判斷：

defaultdict — 自動初始化

from collections import defaultdict

result = defaultdict(list)    # key 不存在時，自動建立空 list

for s in strs:
    key = tuple(sorted(s))
    result[key].append(s)     # 不用判斷，直接 append

✅ defaultdict(list) 的意思是：傳入 list 這個函式。當存取不存在的 key 時，自動呼叫 list() 建立空 list。

常見用法：defaultdict(list)、defaultdict(int)（預設 0）、defaultdict(set)（預設空 set）

完整解法

建立 defaultdict(list)，key 是排序後的 tuple

每個 anagram 群組共享一個 key

遍歷所有字串，計算 key 並分組

tuple(sorted(s)) 當 key，把字串 append 到對應的 list

回傳 dict 的所有 values

每個 value 就是一個 anagram 群組

Group Anagrams — 完整解法

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        result = defaultdict(list)

        for s in strs:
            key = tuple(sorted(s))    # 所有 anagram 會有相同的 key
            result[key].append(s)

        return list(result.values())

⏱ Time: O(n · k log k) n=字串數量, k=平均字串長度💾 Space: O(n · k)

逐步追蹤執行過程

用範例 ["eat","tea","tan","ate","nat","bat"] 走一遍：

執行追蹤

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
result = defaultdict(list)

# 1. "eat" → key = ('a','e','t') → result[('a','e','t')] = ["eat"]
# 2. "tea" → key = ('a','e','t') → result[('a','e','t')] = ["eat", "tea"]
# 3. "tan" → key = ('a','n','t') → result[('a','n','t')] = ["tan"]
# 4. "ate" → key = ('a','e','t') → result[('a','e','t')] = ["eat", "tea", "ate"]
# 5. "nat" → key = ('a','n','t') → result[('a','n','t')] = ["tan", "nat"]
# 6. "bat" → key = ('a','b','t') → result[('a','b','t')] = ["bat"]

# result.values() →
# [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

進階解法：用字母頻率當 key

排序需要 O(k log k)，但其實可以用「26 個字母的頻率陣列」當 key，降到 O(k)：

字母頻率 key — O(n·k)

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        result = defaultdict(list)

        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1   # a=0, b=1, ..., z=25
            result[tuple(count)].append(s)       # list 不能當 key，轉 tuple

        return list(result.values())

ord(c) - ord('a') 是把字母轉成 0-25 的 index 的慣用技巧。
ord('a') = 97，ord('z') = 122，相減就是字母在字母表中的位置。

Group Anagrams 的精髓不是演算法，而是「找到一個能代表整個群組的 key」。這種把問題轉換成 key 設計問題的思維，在後面的 Sliding Window 和 Two Pointers 也會一直出現。

本篇重點整理

🔑Anagram 的共同 key = tuple(sorted(s))，排序後相同就是同組

📦defaultdict(list) — key 不存在時自動建立空 list，省掉 if 判斷

⚠️list 不能當 dict key（可變、不能 hash），要先轉 tuple

🚀進階：26個字母頻率陣列當 key，可從 O(k log k) 降到 O(k)

EP.02 — Set vs Dict

選對資料結構，解題事半功倍

EP.04 — Two Pointers

即將推出

LeetCode

HashMap

defaultdict

Sorting

Python

EP.03

#49 Group Anagramsdefaultdict 的正確用法