題目

Example 1:

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]

Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

給定一個字串陣列 strs，請將所有「anagram」字串分在同一組。

• anagram：相同字母異序詞，指由相同字母組成、順序不同的單字
• 例如："eat", "tea", "ate" 是一組。

解題關鍵觀念：HashMap + 排序後當 Key

• 任何一組 anagram，排序後的結果一定一樣
  • 比如 "eat" → "aet"
  • "tea" → "aet"
  • "ate" → "aet"
• 所以這樣就可以用排序後的字串當作 key，原始字串加進 value 的 list 裡。

程式碼（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams_map = defaultdict(list)
        # 先遍歷每個單字，然後去 sorted 他
        for word in strs:
            single_sorted_word = sorted(word) # sorted 是回傳單個單字的陣列：['a', 'e', 't']...
            key = ''.join(single_sorted_word) # aet,ant...
            # if key not in anagrams_map: # 用 defaultdict 就不用先檢查 key 是否存在了，不存在會直接幫你預測創建預設值
            #     anagrams_map[key] = []
            anagrams_map[key].append(word)
        return list(anagrams_map.values())

處理過程：

Time Complexity & Space Complexity

• Time Complexity: O(n * k log k)

  • n 是字串的數量，k 是每個字串的平均長度
  • 對每個字串進行排序的時間複雜度是 O(k log k)，因此總時間複雜度是 O(n * k log k)

• Space Complexity: O(n * k)

  • 最壞情況下，所有字串都是不同的 anagram，會產生 n 個不同的 key
  • 每個 key 對應一個 list，總共要儲存 n 個長度為 k 的字串
  • 所以總空間為 O(n * k)

為何要用 defaultdict？

1
2

from collections import defaultdict
anagrams_map = defaultdict(list)

當某個 key 不存在時，自動建立對應的空 list。

不用每次都需要去判斷 HashMap 中是否已經有這個 key，簡化程式碼。

1
2

if key not in hashmap:
    hashmap[key] = []

• Next Post →