49. Group Anagrams

Question: Group Anagrams

Solution1

將每個一字串製作 hash_map，方式是用 26 個 0 的 list，字母順序 - 97 為 index，值為字母出現個數 ex: “d” 的 hash map 為 [0, 0, 0, 1, 0, 0, ……]

💡 取得 index 的方式可以用 ASCII
a 的 ASCII 為 97, b 為 98, c 為 99, d 為 100
python 函式中， ord("a") 可以取得 "a" 的 ASCII
因此想要 d 放在 hash map 中 index 為 3 的位置，可以用 ord(”a”) - ord(d) 取得 index = 3 

當讀到 d 的時候 hash_map[3] += 1

再新創一個字典(D)，負責紀錄 key, value

將字串(A)的 hash map (hash A)作為該字典(D) 的 key，value 為 list，存放字串(A)

💡 由於字典的 key 的型態必須是 immutable，list 為 mutable，所以要將 list 轉為 tuple

之後製作找出每一個字串的 hash map，去跟字典(D) 做比對，如果沒有 key 跟 hash map 一樣，就新增，如果有跟 hash map 一樣的 key，就把字串新增到 hash map 的 value 中

這邊的時間複雜度會是 string 的長度 n 乘上 string 的個數 m

O(m * n)

from collections import defaultdict

class Solution:

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

anagram_map = defaultdict(list)

for ele in strs:

ele_map = [0] * 26

for c in ele:

ele_map[ord(c) - ord("a")] += 1

ele_map = tuple(ele_map)

anagram_map[ele_map].append(ele)

return [v for v in anagram_map.values()]

Solution2

think about sorted

string “tan” & “nat” 排序過都為 "ant”

但每一個 string 排序的時間複雜度為 nlogn

如果總共有 m 個 strings，時間複雜度就會是 O(m * nlogn)

留給大家囉！

Video Solution