2021-04-23 21:33:01

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

题目描述

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

示例：

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

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

解题思路

1. 排序 + 哈希表

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

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

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

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)