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 语句中, 不进行排序也可以, 因为题目中说输出的顺序无关紧要.
来源: http://www.bubuko.com/infodetail-3120550.html