LeetCode - Anagrams（字母異位詞分組）

題目描述

給定一組字符串數組 strs，將它們按照字母異位詞進行分組。字母異位詞是指由相同字母組成，但排列順序不同的字符串。

範例：

輸入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出：[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
解釋：字母異位詞如 "eat"、"tea" 和 "ate" 被分為一組，"tan" 和 "nat" 為另一組，"bat" 自成一組。

注意：

• 結果中的每個分組內的字母異位詞順序無關。
• 所有輸入的字母均為小寫。

解法思路

這個問題的核心在於識別字母異位詞的特性，即相同的字母異位詞在排序後會形成相同的字符串。因此，可以將每個字符串排序後作為鍵，將異位詞分組。

1. 排序字符串：對於每個字符串，將其字母排序，生成一個唯一的鍵，所有異位詞經排序後都會變成相同的鍵。
2. 使用字典分組：創建一個字典，鍵為排序後的字符串，值為包含該鍵的字母異位詞列表。
3. 組裝結果：遍歷輸入字符串，將每個字符串按排序後的鍵存入字典中，最後將字典中的值組裝成輸出。

範例代碼

以下是 Python 的實現：

from collections import defaultdict

def groupAnagrams(strs):
    anagrams = defaultdict(list)

    for s in strs:
        # 將字符串排序並轉換為元組以作為鍵
        key = tuple(sorted(s))
        anagrams[key].append(s)

    return list(anagrams.values())

代碼解析

1. 字典結構：使用 defaultdict(list) 來存儲字母異位詞分組。
2. 排序生成鍵：對於每個字符串，排序後作為鍵插入字典中。
3. 返回結果：將字典的值轉換為列表，即所有異位詞分組的列表。

時間和空間複雜度

• 時間複雜度：O(N * K log K)，其中 N 是 strs 中字符串的數量，K 是字符串的最大長度。對每個字符串排序需要 O(K log K) 時間。
• 空間複雜度：O(N * K)，儲存字典中的鍵值對。