LeetCode 49 字母异位词分组

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/group-anagrams/description/

博主Github：https://github.com/GDUT-Rp/LeetCode

题目：

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解题思路：

方法一：每个字符串排序，放到map里整理

对每个str进行排序，放到一个map<string, []string>里，这里的[]string就是答案了

Golang

func groupAnagrams(strs []string) [][]string {strMap := make(map[string][]string)// 逐个取出来然后排序for _, str := range strs {astr := sortString(str)if v, ok := strMap[astr]; ok {v = append(v, str)strMap[astr] = vcontinue}alist := make([]string, 0)alist = append(alist, str)strMap[astr] = alist}// mapvar allList [][]stringfor _, v := range strMap {allList = append(allList, v)}return allList
}func sortString(str string) string {var needSort []bytefor i:=0; i<len(str); i++ {needSort = append(needSort, str[i])}sort.SliceStable(needSort, func(i, j int) bool {return needSort[i] > needSort[j]})return string(needSort)
}

复杂度分析

时间复杂度：$O(nk\log k)$，其中 n 是 $\text{strs}$ 中的字符串的数量，k 是 $\text{strs}$ 中的字符串的的最大长度。需要遍历 $n$ 个字符串，对于每个字符串，需要 $O(k\log k)$ 的时间进行排序以及 $O(1)$ 的时间更新哈希表，因此总时间复杂度是 $O(nk\log k)$。

空间复杂度：$O(nk)$，其中 $n$ 是 $\text{strs}$ 中的字符串的数量，k 是 $\text{strs}$ 中的字符串的的最大长度。需要用哈希表存储全部字符串。

方法二：技数

对每个字符串的字母取频数，cnt[26]作为key，进行统计整理 map<cnt[26], []string>

Golang

func groupAnagrams(strs []string) [][]string {cntMap := make(map[[26]int][]string)for _, str := range strs {cnt := [26]int{}for _, s := range str {cnt[s - 'a']++}cntMap[cnt] = append(cntMap[cnt], str)}var result [][]stringfor _, v := range cntMap {result = append(result, v)}return result
}

复杂度分析

时间复杂度：$O(n(k+|\Sigma |))$，其中 n 是 $\text{strs}$ 中的字符串的数量，k 是 $\text{strs}$ 中的字符串的的最大长度，$\Sigma$ 是字符集，在本题中字符集为所有小写字母，$|\Sigma |=26$。需要遍历 n 个字符串，对于每个字符串，需要 $O(k)$ 的时间计算每个字母出现的次数，$O(|\Sigma |)$ 的时间生成哈希表的键，以及 $O(1)$ 的时间更新哈希表，因此总时间复杂度是 $O(n(k+|\Sigma |))$。

空间复杂度：$O(n(k+|\Sigma |))$。