[python 刷题] 49 Group Anagrams

[python 刷题] 49 Group Anagrams

题目：

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

这里 Anagram 的定义就是可以通过重新排序获得的单词，如 cat 可以获得 act 这种，所以这道题需要按需将所有 Anagram 组合在一起，如：

["eat","tea","tan","ate","nat","bat"] 中包含

• {'a': 1, 'e': 1, 't': 1} 为 key 的 [eat, tea, ate]
• {'b': 1, 'a': 1, 't': 1} 为 key 的 [bat]
• {'t': 1, 'a': 1, 'n': 1} 为一组的 [tan, nat]

所以，最终的答案就是 [["bat"],["nat","tan"],["ate","eat","tea"]]

我最初的写法是：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # if no list, return empty
        if len(strs) == 0:
            return strs

        ana_dict = {}

        for str in strs:
            key = {}
            for c in str:
                key[c] = key.get(c, 0) + 1

            frozen_key = frozenset(key.items())
            if frozen_key in ana_dict:
                ana_dict[frozen_key].append(str)
            else:
                ana_dict[frozen_key] = [str]

        res = []
        for _, value in ana_dict.items():
            res.append(value)

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这个写法的逻辑为：

1. 便利每一个 key，将其转换为对应的 dict
2. 因为 dict 可变（mutable），python 的 dict 要求 key 不可变，因此将其转化为 immutable 的 frozenset
3. 遍历 dict 生成最终结果

这是一个可以实行的方法，大 O 是 $O(n\times k)$，其中 $n$ 为数组的长度，$k$ 为字符串的长度

随后我又看了一下别人是怎么写的，然后发现了更妙的两个写法：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # if no list, return empty
        if len(strs) == 0:
            return strs

        ana_dict = {}

        for str in strs:
            key = ''.join(sorted(list(str)))
            ana_dict[key] = ana_dict.get(key, [])
            ana_dict[key].append(str)

        res = []
        for _, value in ana_dict.items():
            res.append(value)

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个就不把遍历的 str 转换成 dict，而是直接通过排序的方式获得 Anagram，理论上来说这个写法的时间复杂度为 $O(n\times klog(k))$，不过我实际提交了几次，发现 leetcode 上这个写法的平均用时比第一个写法要短，可能有三个原因：

• dict 转 frozenset 太耗时了
• python 内部对 sort 的优化
• leetcode 的案例比较极端

第二个写法更妙一些，它最终的时间复杂度还是 $O(n\times k)$，不过写法更简洁:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)

        for str in strs:
            count = [0] * 26
            for c in str:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(str)

        return ans.values()
1
2
3
4
5
6
7
8
9
10
11

这里主要用了一些比较妙的点：

• 使用了 collections.defaultdict

  collections.defaultdict 和 dict 主要的区别就在于，前者当遇到当前 dict 中不存在的 key，会使用提供的默认值，而 dict 就会直接报错

  以本题为例，ans = collections.defaultdict(list) 代表着所有 key 的默认初始值为 []，也就可以直接使用 append 方法

• 与其使用 dict 去创建 k-v 对，不如直接使用 array，毕竟英文就 26 个字母

• 没有 frozenset 去创建不可变的 key，而是使用了 tuple

  对于数量比较小——这里就 26 个字母——的 iterable 来说，tuple 一般来说会比 frozenset 快一些

• 直接使用内置的 values() 进行返回，而没有做一个新的迭代

当然，实际运行上，这个跑法还是比用 sort 的要慢一点，但是比我之前写的那个方法要快一点点，不过写法则是干净很多