变位词分组

字符串

说明

把字符排序后的结果作为分组键；相同字母组成的词会落入同一组。

分析

把每个词拆成 rune 后排序，排序结果作为规范化键；字符组成相同的词会得到同一个键。用 map 收集相应分组，最后按键取出结果。

图解推演

eat 与 tea 的 rune 排序结果都为 aet，所以共享同一 map 键；cat 得到 act，单独一组。该键保存字符及重复次数，比“字符集合”更准确，例如 abb 与 ab 不能归为一组。Unicode 规范等价形式不会自动归一化，如业务需要应先明确规范化规则。

查看图表代码

适用前提与边界

排序每个长度为 m 的词需要 O(m log m)；固定小字符集也可用计数向量作键。

示例输入与调用

groups := GroupAnagrams([]string{"eat", "tea", "cat"})
	fmt.Println(groups["aet"])

运行输出

[eat tea]

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

func GroupAnagrams(words []string) map[string][]string {
	groups := map[string][]string{}
	for _, w := range words {
		chars := []rune(w)
		sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
		key := string(chars)
		groups[key] = append(groups[key], w)
	}
	return groups
}

func main() {
	groups := GroupAnagrams([]string{"eat", "tea", "cat"})
	fmt.Println(groups["aet"])
}