力扣 49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
方案一：用长度为 26 的计数数组保存每个单词的字母出现次数，然后将其作为 key，用无序映射保存。（部分语言不支持）
func groupAnagrams(strs []string) (ans [][]string) {
// 用数组作为 map 的 key (部分语言不支持)
mp := make(map[[26]int][]string, len(strs))
// 遍历 strs
for _, str := range strs {
// 定义长度为 26 的数组
key := [26]int{}
// 遍历单词，将组成单词的字母的出现次数保存到数组
for _, v := range str {
key[v - 'a']++
}
// 将当前单词保存到 map 中
mp[key] = append(mp[key], str)
}
for _, v := range mp {
ans = append(ans, v)
}
return
}
- 时间复杂度：O(n)，因为需要遍历所有单词，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了长度不超 n 的无序映射，所以空间复杂度为 O(n)。
方案二：将每个单词的组成字母排序，再将排序后的字母组成无序映射 map 的 key，遍历所有单词构建无序映射。
func groupAnagrams(strs []string) (ans [][]string) {
// 定义无序映射
// key 为将单词字母排序后重组成的字符串，val 为组成字母由 key 构成的单词集合
mp := make(map[string][]string)
// 遍历所有单词
for _, str := range strs {
// 将单词格式转化为字节数组（将单词拆分为字母）
arr := []byte(str)
// 使用自定义排序算法，使得所有组成单词的字母顺序排序
sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j]})
key := string(arr)
mp[key] = append(mp[key], str)
}
// 构建答案
for _, v := range mp {
ans = append(ans, v)
}
return
}
- 时间复杂度：O(n)，因为需要遍历所有单词，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了长度不超 n 的无序映射，所以空间复杂度为 O(n)。