字母分拣工厂 · 异位词分组

怎样从“把 ["eat","tea","tan","ate","nat","bat"] 中互为字母异位词的字符串分到同一组。”推导出 哈希分组 · key 身份证设计，并证明每次状态变化都不会漏掉答案？

中心结论：传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。

给出一个字符串数组，要求对字符串数组里面有 Anagrams 关系的字符串进行分组。Anagrams 关系是指两个字符串的字符完全相同，顺序不同，两者是由排列组合组成。

在本站主例中，把 ["eat","tea","tan","ate","nat","bat"] 中互为字母异位词的字符串分到同一组。

算法最终需要得到或观察：得到 3 组:{eat,tea,ate}、{tan,nat}、{bat}。

逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“哈希记忆表”，明确答案需要观察什么。
2. 2状态只维护 当前词、生成 key、map( key → 原词列表 )、活跃仓库桶。
3. 3转移每一步按照 传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。
4. 4收尾读取 得到 3 组:{eat,tea,ate}、{tan,nat}、{bat}。，并复核边界与复杂度。

先问未来需要查询什么，再决定 map 的 key 与 value。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：当前词、生成 key、map( key → 原词列表 )、活跃仓库桶。

这道题可以将每个字符串都排序，排序完成以后，相同 Anagrams 的字符串必然排序结果一样。把排序以后的字符串当做 key 存入到 map 中。遍历数组以后，就能得到一个 map，key 是排序以后的字符串，value 对应的是这个排序字符串以后的 Anagrams 字符串集合。最后再将这些 value 对应的字符串数组输出即可。

传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。

执行过程中持续维护：当前词、生成 key、map( key → 原词列表 )、活跃仓库桶。

正确性依赖以下不变量：两个单词同组 ⇔ 它们生成的 key 相同。

面试时可以压缩为：用 HashMap 分组;关键是规范化 key——排序后 eat/tea/ate 都是 aet,原词 append 到 map[key];字符集固定时可用 26 位计数优化到 O(n·k)。

落到当前题，执行机制可以压缩为：传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入把 ["eat","tea","tan","ate","nat","bat"] 中互为字母异位词的字符串分到同一组。 因为：传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。
2. 2'eat' 的 key = 'aet'异位词排序后一定相等,所以排序结果就是天然的分组键。 因为：key 设计是哈希分组的核心:让「同组」等价于「key 相等」。
3. 3'tea' 的 key = 'aet'异位词排序后一定相等,所以排序结果就是天然的分组键。 因为：key 设计是哈希分组的核心:让「同组」等价于「key 相等」。
4. 4'tan' 的 key = 'ant'异位词排序后一定相等,所以排序结果就是天然的分组键。 因为：key 设计是哈希分组的核心:让「同组」等价于「key 相等」。
5. 5'ate' 的 key = 'aet'异位词排序后一定相等,所以排序结果就是天然的分组键。 因为：key 设计是哈希分组的核心:让「同组」等价于「key 相等」。
6. 6'nat' 的 key = 'ant'异位词排序后一定相等,所以排序结果就是天然的分组键。 因为：key 设计是哈希分组的核心:让「同组」等价于「key 相等」。
7. 7'bat' 归入 key 'abt'按 key 把词追加到对应组。 因为：map 的 value 是列表,实现「一个 key 对多个值」。
8. 8收尾与复杂度得到 3 组:{eat,tea,ate}、{tan,nat}、{bat}。 因为：时间 O(n·k log k) 排序 key · O(n·k) 计数 key · 空间 O(n·k)。传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "sort"

type sortRunes []rune

func (s sortRunes) Less(i, j int) bool {
	return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s sortRunes) Len() int {
	return len(s)
}

func groupAnagrams(strs []string) [][]string {
	record, res := map[string][]string{}, [][]string{}
	for _, str := range strs {
		sByte := []rune(str)
		sort.Sort(sortRunes(sByte))
		sstrs := record[string(sByte)]
		sstrs = append(sstrs, str)
		record[string(sByte)] = sstrs
	}
	for _, v := range record {
		res = append(res, v)
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="group-anagrams", words=["eat","tea","tan","ate","nat","bat"]
    //    期望：得到 3 组:{eat,tea,ate}、{tan,nat}、{bat}。
    //
    // 2. 失败 / 未命中
    //    检查：直接用原字符串当 key 会把 eat 和 tea 拆开。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC242 有效字母异位词；LC128 最长连续序列
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意把 ["eat","tea","tan","ate","nat","bat"] 中互为字母异位词的字符串分到同一组。
2. 2重复逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。
3. 3优化传送带单词经标准化机器生成顺序无关 key(排序或 26 位计数),按 key 把原词追加进 HashMap 仓库桶。
4. 4证明两个单词同组 ⇔ 它们生成的 key 相同。
5. 5复杂度时间 O(n·k log k) 排序 key · O(n·k) 计数 key，空间 O(n·k)