49. 字母异位词分组

难度

中等

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1

输入：

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出：

[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
  • 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
  • 字符串 "ate"、"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2

输入：

strs = [""]

输出：

[[""]]

示例 3

输入：

strs = ["a"]

输出：

[["a"]]

提示

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

解法一：使用 defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict1 = defaultdict(list)
        for i in strs:
            key = ''.join(sorted(i))
            dict1[key].append(i)
        return list(dict1.values())

解法二：使用普通字典

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}  # 普通字典

        for s in strs:
            key = ''.join(sorted(s))

            if key not in dic:  # 手动判断
                dic[key] = []

            dic[key].append(s)

        return list(dic.values())

作者笔记

在 Python 里面，defaultdict 可以直接建立一个新字典。它会自动做这 2 步：

  1. 发现 "aet" 不存在。
  2. 自动给它创建一个空列表 []，然后把 "eat" 加进去。

如果使用普通字典，直接执行 dict1[key].append(i) 可能会报错，因为程序发现没有例如 aet 这样的 key。而 defaultdict 可以自动新建一个 key。

对于这行代码：

key = ''.join(sorted(i))
  • sorted(i) 是排序，把字符按顺序从小到大排。例如 eat、aet、tea 都会排列成 aet，方便用作查找的 key。
  • ''.join(...) 是把后面的字符拼接起来，用空字符串 '' 作为连接符。

'' 是什么

'' 就是空字符串，里面什么都没有，是一对单引号，中间空着。

.join() 是什么用法

join 是字符串的方法，作用是把一个列表里的所有元素拼接成一个完整字符串。

比如有个排好序的字母列表：

lst = ['a', 'e', 't']

执行：

res = ''.join(lst)

意思是：用空字符串把 a、e、t 连起来，中间不加任何东西。

结果：

'aet'

dict1[key].append(i) 的意思是：先在 key 里面找有没有符合的分组，有就把 i 追加进去。append 是在列表最后加一个元素；如果没有，就新建一个 key，再把 i 追加进去。