1 題目描述

給定多個字串，然後把它們分類。只要字串所包含的字元完全一樣就算一類，不考慮順序。

2 解法

2.1 我的解法

因為不考慮順序，只要字串的字元完全一樣就算一類，這讓我最先想到 Set 這個資料結構。我們可以把字串轉成 Set ，想辦法讓 Set 變成 dict 的 key ，然後把相同 key 的字串放在一起。最後再把這些字串放在一個 List 中，這樣就可以得到答案了。但是 Set 是不可 hash 的，所以我們可以先把 Set 裡面的每個元素進行 hash 並相加，這也可以成功的讓。

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ans_dic = {}
        ans = []
        for str in strs:
            str_hash = sum([hash(char) for char in str]) # 把每個字元 hash 並相加 順序就不影響了
            if ans_dic.get(str_hash):
                ans_dic[str_hash].append(str)
            else:
                ans_dic[str_hash] = [str]
        for v in ans_dic.values():
            ans.append(v)
        return ans

時間複雜度 O(nL)

計算哈希值：對於每個字符串，計算哈希值的時間複雜度是 O(L)，其中 L 是字符串的平均長度。
且列表的長度為 n，那麼這一步的總時間複雜度是 O(n) * O(L) = O(nL)

空間複雜度 O(nL)

字典 ans_dic：這個字典最多會存儲 n 個鍵值對，每個鍵是哈希值（整數），每個值是字符串列表。我們會需要一個空間L把每個經過hash的字母相加，空間複雜度是 O(nL)。
結果列表 ans：會包含所有的字串，空間複雜度是 O(n)。

2.2 解法2

但是還有一種可能是 hash 加總後發生碰撞，儘管他們字串不同，但仍有機率會被歸類在同一類。這時候我們可以使用一個更好的方法，就是把字串排序後再 hash ，這樣就可以保證不會發生碰撞。

class Solution(object):
    def groupAnagrams2(self, strs):
        anagram_map = defaultdict(list)

        for word in strs:
            sorted_word = ''.join(sorted(word))
            anagram_map[sorted_word].append(word)

        return list(anagram_map.values())