题目描述

[EN | CN]

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

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明:

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

解法 1:字符串排序

一个比较直接的思路是,将每个字符串的字符都排好序,那么每组 字母异位词 排好序之后的字符串应该是相同的。我们可以基于该性质维护一个 dict,保存从“排好序的字符串”到“原字符串”数组的映射,然后扫一遍所有字符串进行分类即可。

假设字符串总数为 $n$,平均长度为 $m$,那么

  • 时间复杂度为 $O(n m \log m)$,其中的 $m\log m$ 是排序的代价;
  • 空间复杂度为 $O(nm)$,保存结果。

实现与结果如下:

1
2
3
4
5
6
7
from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ret_dict = defaultdict(lambda: [])
        for s in strs:
            ret_dict[''.join(sorted(s))].append(s)
        return [v for v in ret_dict.values()]
  • 执行用时:76 ms,在所有 Python3 提交中击败了 59.05% 的用户。
  • 内存消耗:16.6 MB,在所有 Python3 提交中击败了 14.29% 的用户。

解法 2:字符计数

事实上,我们可以用更简单的方式进行分桶。就是不再对每个字符串都字符排序,而是统计每个字符的次数(即按照定义来),具体实现可以是通过一个简单的 counter 计数(Python 内置)。而且,自己实现也很简单,我们观察题目可以发现给定的字符串里面都是「字母」,那其实可以直接用 ASCII 码来简单映射,用一个长度为 26 的数组来保存 26 个字母出现的次数。

假设字符串总数为 $n$,平均长度为 $m$,那么

  • 时间复杂度为 $O(n m)$,$n$ 为遍历每个字符串,$m$ 为遍历字符串中每个字符;
  • 空间复杂度为 $O(nm)$,保存结果。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ret_dict = defaultdict(lambda: [])
        for s in strs:
            counter = [0] * 26
            for c in s:
                counter[ord(c) - ord('a')] += 1
            ret_dict[tuple(counter)].append(s)
        return [v for v in ret_dict.values()]
  • 执行用时:80 ms,在所有 Python3 提交中击败了 55.35% 的用户。
  • 内存消耗:18.6 MB,在所有 Python3 提交中击败了 14.29% 的用户。