LeetCode Group Anagrams 字母異位詞分組 Python 解法

題目

給定字符串數組，將字母相同但順序不同的字符串分組。所有輸入小寫。組內及組間順序不限，但通常要求組內按字典序排序。

示例：["eat","tea","tan","ate","nat","bat"] → [["ate","eat","tea"],["nat","tan"],["bat"]]。

解題思路：排序鍵分組

1. 對每個字符串排序，得到標準鍵（如 "eat"、"tea" 都變 "aet"）。
2. 用哈希表 map[key] = list 收集同鍵字符串。
3. 最後將哈希表所有值取出，每組再排序，構成結果。

Python AC 代碼

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for s in strs:
            key = ''.join(sorted(s))
            groups.setdefault(key, []).append(s)
        # 組內排序
        return [sorted(v) for v in groups.values()]

# 測試
if __name__ == "__main__":
    ans = Solution().groupAnagrams(["eat","tea","tan","ate","nat","bat"])
    # 順序可能不同，僅驗證分組正確性
    expected = [['ate','eat','tea'], ['nat','tan'], ['bat']]
    assert sorted([sorted(g) for g in ans]) == sorted([sorted(g) for g in expected])

複雜度

• 時間：O(N * K log K)，N 為字符串數，K 為最大長度（排序耗時）。
• 空間：O(N * K) 存儲所有字符串與鍵。

優化方向

若字符集固定（小寫字母），可用 26 維計數元組作鍵，避免排序，時間降為 O(N * K)。