49. 字母异位词分组

https://leetcode-cn.com/problems/group-anagrams/

解法一：

类似242.有效的字母异位词

sorted之后相等的词即是同一组异位词。

>>> s = 'bate'
>>> sorted(s)
['a', 'b', 'e', 't']

将字符串传入py的sorted函数，会返回一个列表，里面的字符按序排列 然后将其作为键存入字典中，值为字符串列表。每次对一个新串，排列后与字典键比较，存入键相同的列表中

这里用了一个defaultdict，需要引入collections包。其作用是免除了键值不存在时的初始化，例如用字典统计词频时，每次都要判断键值是否存在。defaultdict（）传入一个函数，用于键值初次填入时的默认值：

>>> from collections import defaultdict
>>> dd = defaultdict(list)
>>> dd
defaultdict(<type 'list'>, {})
>>> dd['foo']
[]
>>> dd
defaultdict(<type 'list'>, {'foo': []})
>>> dd['bar'].append('quux')
>>> dd
defaultdict(<type 'list'>, {'foo': [], 'bar': ['quux']})

此外还要注意，sorted（）将字符串排序后返回的是list，而list是不可哈希的，不能用于键值，很好理解，以为list是可变的，应该转为tuple。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)  #创建defaultdict
        for s in strs:
            ans[tuple(sorted(s))].append(s)  #注意将sorted返回的结果转成tuple
        return list(ans.values())  #ans的value是dict_values类型，注意转成list

解法二：

原理解法1 差不多。用一个长为26的数组作字典键，值为字符串list。数组统计字符串中每个字符的词频，每组字符串的词频都是一样的，且和其他组不同。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)     
        for s in strs:
            count = [0] * 26  #词频记录
            for c in s:  #统计词频
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)  #注意count要转成tuple
        return list(ans.values())