49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：所有输入均为小写字母。
不考虑答案输出的顺序。
Python solution 1:
import collections
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
groups = collections.defaultdict(list)
for s in strs:
groups[tuple(sorted(s))].append(s)
return map(sorted, groups.values())
分析：
以
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
为例，打印出每一轮 for 循环后 groups 中的情况，如下所示：
groups = defaultdict(<class 'list'>, {('a', 'e', 't'): ['eat']})
groups = defaultdict(<class 'list'>, {('a', 'e', 't'): ['eat', 'tea']})
groups = defaultdict(<class 'list'>, {('a', 'e', 't'): ['eat', 'tea'], ('a', 'n', 't'): ['tan']})
groups = defaultdict(<class 'list'>, {('a', 'e', 't'): ['eat', 'tea', 'ate'], ('a', 'n', 't'): ['tan']})
groups = defaultdict(<class 'list'>, {('a', 'e', 't'): ['eat', 'tea', 'ate'], ('a', 'n', 't'): ['tan', 'nat']})
groups = defaultdict(<class 'list'>, {('a', 'e', 't'): ['eat', 'tea', 'ate'], ('a', 'n', 't'): ['tan', 'nat'], ('a', 'b', 't'): ['bat']})
最终 return 将返回一个 map 对象，它里面保存的结果如下所示：
y = ['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat']
需要注意的是最终groups.value()返回的是以下3个 list：
['eat', 'tea', 'ate'],
['tan', 'nat'],
['bat']
而不是单个单个的单词。
注意对单个单个的英文字母排序时，是按照从a到z的顺序进行排序的；
对字符串进行排序时，则是按照字符串的首字母从a到z的顺序进行排序的。
Python solution 2:
import itertools
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
groups = itertools.groupby(sorted(strs, key=sorted), sorted)
return [sorted(members) for _, members in groups]
分析：
itertools.groupby函数的用法参见：
https://www.cnblogs.com/piperck/p/7219037.html
这里想重点讨论一下key=sorted是什么操作。
sorted本来就是排序，key通常是为排序提供一种依据，比如考虑如下序列：
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
比较以下两种排序的结果：
print(sorted(strs)) # key省略时默认以字母的字典序为排序标准
# 输出为：['ate', 'bat', 'eat', 'nat', 'tan', 'tea']
print(sorted(strs, key=sorted)) # 以排序为依据对strs进行排序
# 输出为：['bat', 'eat', 'tea', 'ate', 'tan', 'nat']
什么是“以排序为依据进行排序”呢？注意到这里的key=sorted是作用在strs中每个元素上的，在strs中，'eat'、'tea' 及 'ate' 这三个字符串之间存在“字母的排序现象”，所以这三个单词可以看作是一个“与排序相关的组”。同理，'nat' 及 'tan' 可以看作是另一个“与排序相关的组”。此时 strs 中剩余的最后一个单词独自形成了一个“与排序相关的组”。
因此，当以 sorted 为依据对 strs 进行排序时，排序的结果就会得到上面所展示的那种情况。
排完序之后，当调用itertools.groupby函数时，又一次用到了key=sorted，这里分组的依据依旧是“排序”。根据前面的分析，依据“排序”可以将 strs 分成三组：'eat'、'tea' 及 'ate'； 'nat' 及 'tan'； 'bat'。
需要注意的是，这里的 key 是 sorted，因此将分组后的 groups 打印出来，将会是以下结果：
key = ['a', 'b', 't']
value = ['bat']
key = ['a', 'e', 't']
value = ['eat', 'tea', 'ate']
key = ['a', 'n', 't']
value = ['tan', 'nat']
return 语句中，不进行排序也可以，因为题目中说输出的顺序无关紧要。