AI毛毛的blog

leetcode打卡-0049字母异位词分组

题目描述

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入:[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出:[[“ate”,”eat”,”tea”],[“nat”,”tan”],[“bat”]]

解题思路

1. 排序 + 哈希表

这道题的解法,是一个分类的过程,物以类聚,就要从表面不同的对象中找到它们的共同点,才可以归为一类。

所以字母异位词的字母是一样的,只是顺序不同,那么将他们重新排列后,就可以变为同值的对象。于是将排序后的对象作为哈希表的键,将对应的原始字符串存储到值列表中,即可满足条件。

由于Python中字典的键是不可变对象,所以还要将排序后的字符串转为元组处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
# 手动管理字典的方法
# hashmap = {}
# for val in strs:
# key = tuple(sorted(val))
# hashmap[key] = hashmap.get(key, []) + [val]
# return list(hashmap.values())

# 利用标准库里的defaultdict更简单一些
hashmap = collections.defaultdict(list)
for val in strs:
hashmap[tuple(sorted(val))].append(val)

return list(hashmap.values())
  • 时间复杂度: O(nklogk),其中n是strs中的字符串的数量,k是strs中的字符串的的最大长度
  • 空间复杂度: O(nk)