LeetCode 49 - 字母异位词分组（Group Anagrams）

问题描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例

示例 1:

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

示例 2:

1 2	输入: strs = [""] 输出: [[""]]

示例 3:

1 2	输入: strs = ["a"] 输出: [["a"]]

约束条件

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

解题思路

这道题的核心是如何判断两个字符串是否为字母异位词。字母异位词的特点是：它们包含完全相同的字母，且每个字母出现的次数也相同。基于这一特点，我们有两种主要解法。

解法一：排序

最直观的方法是对每个字符串进行排序。如果两个字符串是字母异位词，那么排序后它们将完全相同。我们可以使用排序后的字符串作为哈希表的键，将原始字符串添加到对应的分组中。

具体步骤：

创建一个哈希表，键为排序后的字符串，值为原始字符串列表
遍历输入的字符串数组
对每个字符串进行排序，得到排序后的字符串
将原始字符串添加到哈希表中对应键的列表中
返回哈希表中所有的值列表

解法二：计数

排序的方法简单直观，但时间复杂度较高。我们可以通过统计每个字符串中字符的出现次数来优化。由于题目限定只包含小写字母，我们可以使用一个长度为 26 的数组来记录每个字符的出现次数。

具体步骤：

创建一个哈希表，键为字符计数数组，值为原始字符串列表
遍历输入的字符串数组
对每个字符串，创建一个长度为 26 的计数数组，统计每个字母出现的次数
将计数数组作为键，将原始字符串添加到哈希表中对应的列表中
返回哈希表中所有的值列表

实现细节

解法一：排序

在 Go 语言中，我们可以使用 sort 包对字符串进行排序。但需要注意的是，Go 的字符串是不可变的，我们需要先将其转换为字节切片，排序后再转回字符串。

func sortStr(s string) string {
    s2 := []byte(s)
    sort.Slice(s2, func(i, j int) bool {
        return s2[i] < s2[j]
    })
    return string(s2)
}

然后，我们使用排序后的字符串作为哈希表的键：

func groupAnagrams(strs []string) [][]string {
    hashTable := make(map[string]int, 0)
    res := make([][]string, 0)
    for _, str := range strs {
        sortedStr := sortStr(str)
        if index, ok := hashTable[sortedStr]; ok {
            res[index] = append(res[index], str)
        } else {
            res = append(res, []string{str})
            hashTable[sortedStr] = len(res) - 1
        }
    }
    return res
}

解法二：计数

在计数方法中，我们使用一个长度为 26 的整数数组来统计每个字母出现的次数：

func groupAnagrams(strs []string) [][]string {
    mp := map[[26]int][]string{}
    for _, str := range strs {
        cnt := [26]int{}
        for _, b := range str {
            cnt[b-'a']++
        }
        mp[cnt] = append(mp[cnt], str)
    }
    ans := make([][]string, 0, len(mp))
    for _, v := range mp {
        ans = append(ans, v)
    }
    return ans
}

在这个实现中，我们使用 [26]int 类型的数组作为哈希表的键。在 Go 中，数组是可比较的，可以作为哈希表的键，而切片则不行。

方法比较

方面	解法一：排序	解法二：计数
时间复杂度	O(n * k * log(k))	O(n * k)
空间复杂度	O(n * k)	O(n * k)
优点	思路简单直观	更高效，尤其是对于长字符串
缺点	对于长字符串效率较低	实现稍微复杂一些
推荐度	★★★☆☆	★★★★★

其中，n 是字符串数组的长度，k 是字符串的平均长度。

复杂度分析

解法一：排序

时间复杂度：$O(n \times k \times \log(k))$，其中 n 是字符串数组的长度，k 是字符串的平均长度。对每个字符串排序需要 $O(k \times \log(k))$ 的时间，总共有 n 个字符串。
空间复杂度：$O(n \times k)$，需要存储所有字符串。

解法二：计数

时间复杂度：$O(n \times k)$，其中 n 是字符串数组的长度，k 是字符串的平均长度。我们需要遍历每个字符串中的每个字符。
空间复杂度：$O(n \times k)$，需要存储所有字符串。

关键收获

字母异位词的本质：字母异位词本质上是包含相同字母且每个字母出现次数相同的字符串。
哈希表的应用：这道题展示了哈希表在分组问题中的典型应用。
键的选择：在使用哈希表时，选择合适的键是关键。这里我们可以使用排序后的字符串或字符计数数组作为键。
Go语言特性：在 Go 中，数组是可比较的，可以作为哈希表的键，而切片则不行。这是一个需要注意的语言特性。
时间复杂度优化：通过使用计数方法而不是排序，我们可以将时间复杂度从 $O(n \times k \times \log(k))$ 降低到 $O(n \times k)$。

这道题是哈希表应用的经典例题，掌握了这道题的解法，对于其他涉及字符串分组或字母异位词的问题也会有很好的帮助。