题目
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解析
第一种方法是排序+哈希法:
func groupAnagrams(strs []string) [][]string {
tmpMap := make(map[string][]string)
for _, str := range strs {
s := []byte(str)
sort.Slice(s, func(i, j int) bool {
return s[i] < s[j]
})
sortedStr := string(s)
tmpMap[sortedStr] = append(tmpMap[sortedStr], str)
}
ans := make([][]string, 0)
for _, v := range tmpMap {
ans = append(ans, v)
}
return ans
}
上面因为每个都需要排序,不是最优解,可以通过将str转化成数组及其出现的次数来当map的key:
func groupAnagrams(strs []string) [][]string {
tmpMap := make(map[[26]int][]string)
for _, str := range strs {
tmp := [26]int{}
for _, c := range str {
tmp[c-'a']++
}
tmpMap[tmp] = append(tmpMap[tmp], str)
}
ans := [][]string{}
for _, v := range tmpMap {
ans = append(ans, v)
}
return ans
}