Go语言字母异位词分组算法详细解析

下面我将从算法思路、代码结构、执行流程、复杂度分析和优化方向五个方面，详细解析这段Go语言实现的字母异位词分组算法。

1. 算法思路

核心思想

字母异位词的特点是字母组成相同但排列顺序不同。基于此特点，我们可以：

1. 将每个字符串排序，排序后的字符串作为异位词的统一标识
2. 使用哈希表（map）存储：排序后字符串 → 原始字符串列表的映射
3. 最后收集哈希表中的所有值作为结果

为什么这样设计？

• 排序：将不同顺序但相同字母组成的字符串统一化
• 哈希表：提供O(1)时间复杂度的查找和插入操作
• 分组收集：直接提取哈希表的值就是所需结果

2. 代码结构解析

import (
    "sort"
    "strings"
)

func groupAnagrams(strs []string) [][]string {
    // 1. 初始化哈希表
    groups := make(map[string][]string)
    
    // 2. 遍历所有字符串
    for _, str := range strs {
        // 2.1 字符串排序
        s := strings.Split(str, "")
        sort.Strings(s)
        sortedStr := strings.Join(s, "")
        
        // 2.2 分组存储
        groups[sortedStr] = append(groups[sortedStr], str)
    }
    
    // 3. 结果收集
    result := make([][]string, 0, len(groups))
    for _, v := range groups {
        result = append(result, v)
    }
    
    return result
}

关键部分解析

1. 字符串排序处理：

   s := strings.Split(str, "")  // 将字符串拆分为字符切片
   sort.Strings(s)             // 对字符切片排序
   sortedStr := strings.Join(s, "") // 重新组合为字符串

   • strings.Split(str, "")：将字符串拆分为单个字符组成的切片
   • sort.Strings(s)：对字符切片进行字典序排序
   • strings.Join(s, "")：将排序后的字符切片重新组合为字符串

2. 哈希表分组：

   groups[sortedStr] = append(groups[sortedStr], str)

   • 使用排序后的字符串作为key
   • 将原始字符串追加到对应的分组中

3. 结果收集：

   result := make([][]string, 0, len(groups))
   for _, v := range groups {
       result = append(result, v)
   }

   • 预分配足够容量的切片（性能优化）
   • 遍历哈希表的值并收集到结果切片中

3. 执行流程示例

以输入 ["eat","tea","tan","ate","nat","bat"] 为例：

最终结果：[["eat","tea","ate"],["tan","nat"],["bat"]]

4. 复杂度分析

时间复杂度

• 字符串排序：O(klogk)，k是字符串长度
• 遍历所有字符串：O(n)
• 总时间复杂度：O(n*klogk)

空间复杂度

• 哈希表存储：O(n*k)
• 总空间复杂度：O(n*k)

其中：

• n：字符串数量
• k：字符串的平均长度

5. 优化方向

1. 计数法优化（避免排序）

func groupAnagrams(strs []string) [][]string {
    groups := make(map[[26]int][]string)
    
    for _, str := range strs {
        count := [26]int{}
        for _, c := range str {
            count[c-'a']++
        }
        groups[count] = append(groups[count], str)
    }
    
    result := make([][]string, 0, len(groups))
    for _, v := range groups {
        result = append(result, v)
    }
    return result
}

优势：

• 时间复杂度降为O(n*k)
• 特别适合长字符串的情况

注意：

• Go中数组可以作为map key（切片不行）
• 需要处理Unicode时需扩展计数数组

2. 并行处理

对于超大字符串数组，可以：

1. 将输入切片分成多个块
2. 使用goroutine并行处理每个块
3. 合并各个goroutine的结果

6. 关键点总结

1. 排序是关键：通过排序将异位词统一化
2. 哈希表高效分组：利用O(1)的查找和插入

3. Go语言特性：

   • strings.Split/Join处理字符串
   • sort.Strings进行排序
   • map的灵活使用

4. 性能考量：

   • 预分配结果切片容量
   • 考虑字符串长度选择排序法或计数法

这个实现充分展示了Go语言在处理字符串和哈希表方面的能力，代码清晰且效率较高。