字母异位词分组
Group Anagrams
把字符串数组按字母异位词分组；字母相同、顺序不同视为同一组。
在力扣中练习题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成
"bat"。 - 字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。 - 字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
解题思路
排序键 + 哈希表
异位词排序后长得一模一样
最直接的做法是两两比较两个单词是否互为异位词，时间是 O(n² · k)，单词一多就慢。
关键观察：两个单词互为异位词，当且仅当它们排序后的字符串相同。于是可以给每个单词算一个规范键，用哈希表把键相同的单词收集到一起。
自拟主例 ["abc","bca","cab","dog","god","x"]：前三个都排序成 abc，dog 和 god 都排序成 dgo，x 单独成组。
"abc" 排序后是 "abc"，新建一组。
- key
- abc
- 组数
- 1
每个单词排序 O(k log k)，哈希查找期望 O(1)，总时间 O(n · k log k)，空间 O(n · k)。键相同的单词直接追加，不需要再回头比较。
"dog" 排序后是 "dgo"，新建一组。
- key
- dgo
- 组数
- 2
如果字符集很小（例如只有小写字母），可以用 26 个计数拼成键，把排序的 O(k log k) 降到 O(k)。
易错点
- 直接对原字符串排序：会打乱输出顺序，题目要求组内保留原单词。
- 用字符和当键：abc 与 aad 的字符和可能相同，会错误合并。
- 把空串漏掉：空串排序后仍是空串，应单独成组。
计数键 · 不排序
用 26 个字母的出现次数当指纹
时间从 O(n · k log k) 降到 O(n · k)，代价是键更长（26 个计数），适合字符集固定且单词较长的情况。
排序键要付出 O(k log k)。如果字符集固定为 26 个小写字母，可以直接统计每个字母出现几次，把这 26 个数字拼成字符串当键。
例如 abc 和 cab 的计数都是 1#1#1#0#...，键相同；aad 的计数是 2#0#1#...，不会和 abc 混淆。
每个单词扫描一遍 O(k)，拼键 O(26)，总时间 O(n · (k + 26))，空间仍是 O(n · k)。计数键比分隔符要选好，避免 1, 11 和 11, 1 这类拼接歧义。
- 1对每个单词统计 26 个字母的出现次数。
- 2把计数用分隔符拼成 key。
- 3按 key 放入哈希表。
- 4收集所有分组。
易错点
- 计数拼键不加分隔符：不同计数可能拼成同一个字符串。
- 只处理小写字母：题目若含大写或数字，需要扩大计数表。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
strs = ["abc","bca","cab","dog","god","x"]groups 为空；逐个读入单词，把字符排序后得到的字符串当键。
- 组数
- 0
查看 C++ 代码
延伸阅读
- “为每个元素找一个规范键”是哈希分组的通用套路；键必须满足：同组元素键相同，不同组键不同。
- 如果只需要判断两个单词是否互为异位词，比较排序后的字符串或计数数组即可。