49. 字母异位词分组

题目是这样的：给一个字符串数组，把字母异位词分到一组里。字母异位词就是字母出现次数完全一样、只是顺序不同的两个串，比如 eat 和 tea（题目出处：力扣 49 题面）。官方例子：[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] 要分成 [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]。组内顺序和组间顺序都不作要求，怎么排都行。另外两个例子更简单：[“”] 分成 [[“”]]，[“a”] 分成 [[“a”]]。

分组的依据只能是字母出现次数

两个串是不是异位词，只看每个字母出现了几次。eat 和 tea 都是 a、e、t 各出现一次，所以是异位词；tan 含 1 个 n、0 个 e，bat 含 1 个 b、0 个 n，次数分布不一样，所以 tan 和 bat 不是异位词，分组只看次数，不看顺序。

分组于是变成一件事：给每个串算一个“特征”，特征相同的分到一组。特征可以是很多种样子，排好序的串是一种，26 个字母的出现次数也是一种。只要特征满足一条就行：异位词的特征一定相同，不是异位词的特征一定不同，排好序的串和出现次数都满足这一条。

最直接的做法：两两比较

最直接的想法是拿第一个没分组的串，去和后面每一个没分组的串比是不是异位词，比出来的放进同一组，再拿下一个没分组的串继续比。比两个串是不是异位词的办法也直接：数一遍 26 个字母的出现次数，逐个数对一遍。

from collections import Counter

def is_anagram(a, b):
    # 长度不同，出现次数不可能一样，直接判不是
    if len(a) != len(b):
        return False
    return Counter(a) == Counter(b)

def group_naive(strs):
    n = len(strs)
    used = [False] * n
    groups = []
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        group = [strs[i]]
        for j in range(i + 1, n):
            if not used[j] and is_anagram(strs[i], strs[j]):
                used[j] = True
                group.append(strs[j])
        groups.append(group)
    return groups

这份代码是对的，官方三个例子全过，3000 组随机数据和后面的正式解法对拍也没有一组失配（随机种子 20261111，每组 1 到 12 个串，串长 0 到 6，字母表 abc）。但它慢，慢在比较次数是按平方涨的：n 个串要比 n 平方量级的对数。本地实测，2000 个串、串长 20（字母表 abcdef，随机种子 7），这份朴素做法要 7.7651 秒。

特征当钥匙：一遍就分完

两两比较慢，是因为每次都要重新判断“这两个串是不是异位词”。换个做法：每个串只算一次特征，把特征当字典的键，同一个键的串自然就聚到了一起。一遍扫完，分组就完了。

def group_count(strs):
    buckets = {}
    for s in strs:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - ord("a")] += 1
        key = tuple(counts)  # 列表不能当字典的键，转成元组才行
        buckets.setdefault(key, []).append(s)
    return list(buckets.values())

拿官方例子走一遍：eat 的钥匙是 a、e、t 各 1 次、其余 0 次，tea 和 ate 的钥匙跟它一模一样，所以三个串进了同一个桶；tan 的钥匙里 e 是 0 次、n 是 1 次，nat 跟它一样；bat 单独一个桶。最后 buckets 里三个桶，就是答案的三个组。

这份代码只认小写字母：ord(ch) - ord(“a”) 假定每个字符都在 a 到 z 之间，题目给的约束正是串只由小写字母组成。时间是 O(n * k)，n 是串的个数，k 是串长。每个串只数一遍字母，字典操作一次。空间也是 O(n * k)，桶里存的是所有串本身。本地实测，同样 2000 个串、串长 20（随机种子 7），计数做法只要 0.0061 秒，朴素做法的 7.7651 秒连零头都不到。串再多一档，10000 个串、串长 10、字母表 abcdefghij（随机种子 7，用 random.choice 逐个字母生成），计数做法 0.0196 秒，分出 8583 组。

排序当钥匙：写法更短，省不省时间要看串长

特征不止计数一种。把串排好序当钥匙也行：eat 排完是 aet，tea 排完也是 aet，同一个钥匙，自然同一组。

def group_sorted(strs):
    buckets = {}
    for s in strs:
        buckets.setdefault("".join(sorted(s)), []).append(s)
    return list(buckets.values())

这份代码比计数版短，想法也更直观，第一次写这道题我用的就是它。但它多了一次排序，时间是 O(n * k log k)。串短的时候排序便宜，实测反而比计数快：2000 个串、串长 20（随机种子 7），排序版 0.0041 秒，计数版 0.0061 秒；10000 个串、串长 10、字母表 abcdefghij（随机种子 7，用 random.choice 逐个字母生成），排序版 0.0112 秒，计数版 0.0196 秒。串长到 100 就反过来了：5000 个串、串长 100、字母表为 26 个小写字母（随机种子 7），计数版 0.0408 秒，排序版 0.0710 秒。串越长，排序的代价越大，计数的优势才显出来。按题目给的范围，串长最多 100、串最多 10000 个，两种做法都能过，选哪个看串长。短串多就排序，长串多就计数。

三个容易踩的坑

第一个坑是钥匙的类型。26 个出现次数一开始是列表，列表是可变的，不能当字典的键，直接写 buckets[counts] 会报 TypeError。转成元组就行，元组不可变，能当键。排好序的串本身就是字符串，没有这个问题。

第二个坑是空串。空串的钥匙是 26 个 0，两个空串的钥匙一样，会分到一组，这是对的：空串和空串互为异位词。本地实测 [“”, “”] 分出来就是一组 [[“”, “”]]。写代码的时候不用给空串单独开分支，钥匙自己会把它算对。

第三个坑是长度不同的串。长度不同，出现次数加起来就不一样，钥匙一定不同，不用单独判断长度。本地实测 [“aa”, “a”, “aaa”] 分出来是三组，各自一组；[“ab”, “ba”, “ab”, “ba”] 分出来是一组，重复的串也照样分进去，不去重。

复杂度再算一遍

计数版：时间 O(n * k)，每个串数一遍字母；空间 O(n * k)，桶里存全部的串。排序版：时间 O(n * k log k)，每个串排一次序；空间一样是 O(n * k)。朴素版：时间 O(n^2 * k)，比较次数按平方涨；辅助空间 O(n)，只用一个标记数组记哪些串已经分过组，算上返回的分组结果同样是 O(n * k)。

钥匙可以是计数元组，也可以是排好序的串，两种都满足“异位词相同、非异位词不同”这一条，差别只在串长不同的时候谁更快：串长 10 和 20 的时候排序快一点，串长 100 的时候计数反超。