题目描述
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明:
所有输入均为小写字母。
不考虑答案输出的顺序。
算法1
(哈希表+字符串排序) $O(nm\log m)$
问题分析
观察三个异位词 "eat", "tea", "ate"
可以发现,他们的字母组成都是一样的,因此将其按照字母顺序排列将会生成同一个字符串,即 "aet"
。因此,我们可以利用字符串排序来看哪些单词是同一组异位词,利用字典存储排序后的词和同一组的词,例如 {"aet": ["eat", "tea", "ate"]}
。
代码详解 (Python)
from collections import defaultdict
def groupAnagrams(strs):
dict1 = defaultdict(list)
for val in strs:
key = "".join(sorted(val))
dict1[key].append(val)
res = []
for item in dict1:
res.append(dict1[item])
return res
if __name__ == "__main__":
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
res = groupAnagrams(strs)
print(res)