字母异位词分组：排序键或计数键
两两比较异位词是平方次判定。给每个词一个与字母顺序无关的指纹，同指纹的词收进同一组。
把每个词的字符排序，得到的串当哈希键，原词追加进对应列表。互为异位词的词排序结果相同，自然落在同一组。每个词 O(k log k)，整体 O(n·k log k)。字母表固定时，26 维计数拼成的签名也能当键，每个词 O(k)。
这是 LeetCode 49. Group Anagrams。大白话：给你一串小写单词，把互为字母异位词的收进同一组，返回这些组。异位词指字符种类相同、每种字符的个数也相同，只是排列不同。组的顺序、组内顺序题目都不强求。
主例 ["eat","tea","tan","ate","nat","bat"]。eat、tea、ate 三个词都是 a、e、t 各一个，一组；tan、nat 是 a、n、t 各一个，一组；bat 只有自己。三组就是答案。
LC242 只判定两个词。这里有 n 个词，两两调用判定是平方次。缺的不是「怎么判断一对」，而是「怎么让同一类词自己找到对方」——需要一个与排列无关、只与字母计数有关的键。
分组要的是键，不是成对比较
输入是字符串数组，输出是分组后的二维数组。两个词进同一组，当且仅当它们的字符多重集相等。主例里 eat 和 tea 进一组，eat 和 tan 不能进一组：后者多了 n、少了 e。
若对每个词都和其他词做一次 LC242，正确但 O(n²·k)。n 和词长都上来就慢。分组问题的通用缺口是：先把等价类折叠成一个代表元，再用哈希表按代表元收集。
排序串就是指纹
把词里的字符按字典序排开，得到的串只保留「有哪些字母、各几份」，丢掉了原来的排列。两个词互为异位词，当且仅当这个排序串相同。eat 排序得 aet，tea 也是 aet，tan 是 ant。演示三帧依次停在这三个键上。
这个排序串就是哈希表的键。键相同，原词进同一列表。不要把原词当键：eat 和 tea 本身不相等，会拆成两组。也不要只按长度分组：eat 和 tan 一样长，却不是异位词。
指纹排序是归一化：同一个等价类折叠成同一个代表。后面的计数签名是另一种归一化，判定条件相同，只是算键更快。
一张表，边算键边入组
遍历原数组，每个词算一次排序键，append 到 map[key] 的列表末尾。一遍扫描结束，表里有几个键就有几组。组内顺序跟原数组里出现的顺序一致。
用手走主例。eat → aet，表里出现第一组 [eat]。tea → aet，追加成 [eat, tea]。tan → ant，新开一组 [tan]。ate → aet，aet 组变成 [eat, tea, ate]。nat → ant，ant 组变成 [tan, nat]。bat → abt，独自 [bat]。演示从 [eat] 收到两组、再到三组收齐 [eat,tea,ate]、[tan,nat]、[bat]，对应的就是这张表填满的过程。
更快的键：26 维计数签名
排序每个词要 O(k log k)。词很长时，改统计 26 个小写字母的出现次数，再拼成一段不会歧义的签名，例如用 # 隔开的 26 个整数。两个词互为异位词，当且仅当这 26 个数完全一样，因而签名相同。每个词只扫一遍，O(k)。
主例 eat、tea、ate 的计数都是 a1 e1 t1，其余 0，签名相同；tan、nat 是 a1 n1 t1；bat 是 a1 b1 t1。和排序键分出的组一模一样。题目是小写字母时，这是更优的键；面试先写排序键，再补一句计数键，两套都成立。
九行 Go：排序键分组
func groupAnagrams(strs []string) [][]string {m := map[string][]string{}for _, s := range strs {b := []byte(s)sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })m[string(b)] = append(m[string(b)], s)}res := make([][]string, 0, len(m))for _, v := range m { res = append(res, v) }return res}
1键是排序后的新串，值是原词列表。主例 aet 收下 eat、tea、ate。
2必须把 s 拷到 []byte 再排。直接排原串会改输入，也没法当稳定的原词追加。
3append 用的是 s 不是排序后的 b。组里要的是原词。
4最后把 map 的值收成二维切片。组的顺序不重要。
总结
排序键或 26 计数键当指纹，同键同组。主例三组：aet、ant、abt。
- 两两判定是平方。缺口是等价类的代表元，不是再写一遍 LC242。
- eat/tea/ate → aet，tan/nat → ant，bat → abt。不要用原词或长度当键。
- 计数签名每个词 O(k)，排序键 O(k log k)。判定条件相同。