字母异位词分组：Go/Java/Python最优解法详解

问题描述

字母异位词（Anagram）是指由相同字母重新排列组合形成的不同单词。本题要求：

给定一个字符串数组 strs，将其中所有字母异位词组合在一起，可以按任意顺序返回结果列表。

示例：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解题思路

核心思路

字母异位词的特点是字母组成相同但顺序不同。我们可以利用这个特点：

将每个字符串排序，排序后的字符串作为异位词的统一标识
使用哈希表存储：排序后字符串 → 原始字符串列表的映射
最后将哈希表中的所有值收集起来就是结果

复杂度分析

时间复杂度：O(n*klogk)，n是字符串数量，k是字符串最大长度（排序每个字符串的耗时）
空间复杂度：O(nk)，需要存储所有字符串

各语言最优实现

Go实现

import (
    "sort"
    "strings"
)

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    
    for _, str := range strs {
        // 将字符串转为字符数组并排序
        s := strings.Split(str, "")
        sort.Strings(s)
        sortedStr := strings.Join(s, "")
        
        // 将原始字符串加入对应分组
        groups[sortedStr] = append(groups[sortedStr], str)
    }
    
    // 收集结果
    result := make([][]string, 0, len(groups))
    for _, v := range groups {
        result = append(result, v)
    }
    
    return result
}

特点：

使用strings.Split和sort.Strings进行字符串排序
make(map[string][]string)创建哈希表
最后需要将map转为slice

Java实现

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            // 将字符串转为字符数组并排序
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sorted = new String(chars);
            
            // 如果不存在该key，则新建一个列表
            if (!map.containsKey(sorted)) {
                map.put(sorted, new ArrayList<>());
            }
            map.get(sorted).add(str);
        }
        
        return new ArrayList<>(map.values());
    }
}

特点：

使用Arrays.sort()对字符数组排序
需要处理key不存在的情况
new ArrayList<>(map.values())直接转换结果

Python3实现

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    
    for s in strs:
        # 排序字符串作为key
        key = "".join(sorted(s))
        groups[key].append(s)
    
    return list(groups.values())

特点：

使用defaultdict简化代码
sorted(s)直接返回排序后的字符列表
代码最为简洁

边界情况测试

测试用例	说明	预期结果
`[""]`	空字符串	`[[""]]`
`["a"]`	单个字符	`[["a"]]`
`["eat","tea","tan","ate","nat","bat"]`	常规情况	`[["bat"],["nat","tan"],["ate","eat","tea"]]`
`["abc","cba","bac","def","fed"]`	多个分组	`[["def","fed"],["abc","cba","bac"]]`

算法优化思路

计数法优化（避免排序）

我们可以统计每个字符串中各个字母的出现次数，用计数作为key：

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

复杂度分析：

时间复杂度：O(n*k)，n是字符串数量，k是字符串最大长度
空间复杂度：O(nk)

这种方法在字符串较长时效率更高。

实际应用场景

单词游戏：如 Scrabble 等字母排列游戏
文本分析：查找相似单词
密码学：分析字母频率模式
数据清洗：识别和合并相似条目

总结

字母异位词分组问题的核心在于：

找到合适的分组标识（排序后的字符串或字母计数）
使用哈希表高效分组
处理各种边界情况

三种语言的实现展示了不同语言的特性：

Go：显式类型转换较多，性能优秀
Java：类型系统严格，代码稍显冗长
Python：利用高级数据结构，代码最简洁

建议读者：

先理解排序法的思路
尝试实现计数法优化
比较不同语言的实现差异

扩展思考

如果字符串包含Unicode字符，如何修改算法？
如何优化内存使用，特别是处理大量长字符串时？
如何并行化处理这个分组问题？

希望这篇文章能帮助你彻底掌握字母异位词分组问题！如有任何疑问，欢迎在评论区讨论。