LeetCode | 字母异位词分组

排序法#

把字符串里的字符sort排序后，字母异位词会得到同一个结果。所以可以把排序后的字符串作为哈希表的 key。

具体做法：

1. 准备一个字典 mp。
2. 遍历每个字符串 st。
3. 对 st 里的字符排序，得到 key。
4. 把原字符串 st 放进 mp[key] 对应的列表里。

计数法#

字母异位词不一定要排序才能判断，也可以数每个字母出现了几次。

所以可以用一个长度为 26 的数组记录每个小写字母出现次数。这个数组转成元组后，也可以作为哈希表的 key。

计数法避免了排序，所以每个字符串只需要扫描一遍。

复杂度#

这里 n 是字符串数量，k 是单个字符串的最大长度。

• 排序法：
  • 时间复杂度：O(n * k * log(k))
  • 空间复杂度：O(n * k)
• 计数法：
  • 时间复杂度：O(n * k)
  • 空间复杂度：O(n * k)

排序法里的 log(k) 来自排序。对一个长度为 k 的字符串排序，常见排序算法的时间复杂度是 O(k * log(k))。

可以用“归并排序”来理解这个复杂度。假设有 k 个字符要排序：

1
第 1 层：把 k 个字符分成 2 组
2
第 2 层：继续分成 4 组
3
第 3 层：继续分成 8 组
4
...

每往下一层，问题规模大约减半，所以总层数大约是 log(k)。

分完以后还要一层一层合并。每一层合并时，所有字符加起来都会被处理一遍，也就是 k 次左右。

所以可以理解成：

1
每一层处理 k 个字符
2
一共有 log(k) 层
3
总时间复杂度 = O(k * log(k))

Python 的 sorted 底层不是简单的归并排序，而是 Timsort。不过从这道题分析复杂度时，可以按常见排序的 O(k * log(k)) 来理解。

计数法不排序，只扫描每个字符串里的字符。扫描一个长度为 k 的字符串是 O(k)，扫描 n 个字符串就是 O(n * k)。

排序法#

1
from collections import defaultdict
2
from typing import List
3

4

5
class Solution:
6
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
7
        mp = defaultdict(list)
8

9
        for st in strs:
10
            key = "".join(sorted(st))
11
            mp[key].append(st)
12

13
        return list(mp.values())

计数法#

1
from collections import defaultdict
2
from typing import List
3

4

5
class Solution:
6
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
7
        mp = defaultdict(list)
8

9
        for st in strs:
10
            counts = [0] * 26
11
            for ch in st:
12
                counts[ord(ch) - ord("a")] += 1
13
            mp[tuple(counts)].append(st)
14

15
        return list(mp.values())

测试#

1
def normalize(groups):
2
    return sorted(sorted(group) for group in groups)
3

4

5
sol = Solution()
6

7
ans = sol.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
8
assert normalize(ans) == normalize([["bat"], ["nat", "tan"], ["ate", "eat", "tea"]])
9

10
assert normalize(sol.groupAnagrams([""])) == normalize([[""]])
11
assert normalize(sol.groupAnagrams(["a"])) == normalize([["a"]])
12

13
print("PASS")