使用Go语言实现相同字符组成的字符串分组
Go 实现字符组成一致的字符串分组方案
这类需求本质是对字母异位词做归类,核心判定逻辑是:两个字符串如果字符种类、每个字符的出现次数完全一致,无论字符顺序如何,都属于同一组。
常用的可落地实现方式有两种:
方式1:排序生成唯一标识键
这是最通用、易维护的实现思路,适配所有字符类型的字符串(包括中文等多字节字符):
- 实现逻辑:
- 为每个字符串生成一个“排序副本”:把字符串的所有字符按字典序重新排列,排列后的字符串就作为这组异位词的唯一标识键
- 维护一个哈希映射,键为排序后的字符串,值为对应原字符串组成的列表
- 遍历输入的所有字符串,把原字符串追加到对应键的列表下,最终所有列表就是要求的分组结果
- 核心实现代码:
package main import ( "fmt" "sort" ) // groupAnagrams 对输入字符串按字符组成做分组 func groupAnagrams(strs []string) [][]string { groupMap := make(map[string][]string) for _, str := range strs { // 转rune切片,兼容多字节字符避免排序错误 charArr := []rune(str) // 按字典序排序生成唯一键 sort.Slice(charArr, func(i, j int) bool { return charArr[i] < charArr[j] }) key := string(charArr) // 追加原字符串到对应分组 groupMap[key] = append(groupMap[key], str) } // 将哈希表中的所有分组整理为最终输出格式 result := make([][]string, 0, len(groupMap)) for _, group := range groupMap { result = append(result, group) } return result } func main() { input := []string{"kita", "atik", "tika", "aku", "kia", "makan", "kua"} fmt.Println(groupAnagrams(input)) }
针对题目给出的输入,该代码输出的分组和期望结果组成完全匹配:
- 键为
aikt的分组:["kita", "atik", "tika"] - 键为
aku的分组:["aku", "kua"] - 键为
aakmn的分组:["makan"] - 键为
aik的分组:["kia"]
注:Go语言原生map的遍历顺序是随机的,若需要严格匹配示例中的分组排列顺序,可以在最终结果生成后,对二维切片做一层自定义排序即可,不影响分组的正确性。
方式2:字符计数生成唯一标识键
这种方式适合处理长字符串,性能比排序法更优,适合纯小写英文字符串的场景:
- 实现逻辑:
- 对每个字符串,统计26个小写英文字母的出现次数,把统计结果拼接成固定格式的字符串作为唯一键
- 后续哈希映射的匹配、分组逻辑和排序法完全一致
- 优势是不需要对字符串做全量排序,单次遍历就能生成键,时间开销更低
- 核心键生成代码片段:
count := [26]int{} for _, c := range str { // 仅适配小写英文字符串 count[c-'a']++ } // 将计数数组转成字符串作为哈希键 key := fmt.Sprintf("%v", count)
内容的提问来源于stack exchange,提问作者mghifariyusuf
相关产品推荐
相关产品推荐

