Leetcode題解 Python：四月挑戰DAY6 Group Anagrams

Given an array of strings, group anagrams together.

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

把文字做分類，anagrams 意思是「 a word, phrase, or name formed by rearranging the letters of another, such as cinema , formed from iceman.」(google翻譯)

可以透過移動字母，去拼成另外一個字詞。

於是兩詞若是同一個字謎，兩詞中字母出現的種類是相同的，且字母的出現次數是相同。

要保留這兩個數值，就不能破壞詞的長度，於是去掉 set，接下來想到的是 sorted() ，同一字謎的詞都會跑出相同結果。


不過 sorted() 回傳的類型是 list，list是無法作為 set 或是 dict 的key。用 "".join() 或是 tuple轉換後就可以當作key。

確定了鍵從何而來 ，該鍵的值要保存同一字謎的詞，所以是 dict()，dict[key] : list(str)。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        memo = dict()
        for word in strs:
            anagram = "".join(sorted(word))
            if anagram not in memo: memo[anagram] = [word]
            else: memo[anagram].append(word)
        return memo.values()

這種寫法跟前段班有明顯的差距，前段班不外乎使用 defaultdict()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        import collections
        memo = collections.defaultdict(list)
        for word in strs:
            memo[tuple(sorted(word))].append(word)
        return memo.values()

就效率上，使用模組是有幫助的，不過 Leetcode 沒有寫到是否可以使用，或者是能夠載入甚麼模組，對我來說，能夠不用就不用到。如果一定要用的部分，像是取隨機值，才會使用。

解過多次題目之後發現，如果是可用的模組，不使用import也可以直接使用。