给定一个字符串数组,将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词指字母相同,但排列不同的字符串。示例 1:输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]。示例 2:输入: strs = [""],输出: [[""]]。示例 3:输入: strs = [“a”],输出: [[“a”]]。
自然智慧。
方法一:对字符串排序,放哈希表。
方法二:记字符串的字符个数,放哈希表。
这两种方法,本质都是一样的。
代码用golang编写。代码如下:
package main
import (
"fmt"
"sort"
)
func main() {
strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
ret := groupAnagrams1(strs)
fmt.Println(ret)
ret = groupAnagrams2(strs)
fmt.Println(ret)
}
func groupAnagrams1(strs []string) [][]string {
map0 := make(map[string][]string)
for _, str := range strs {
record := make([]int, 26)
for _, cha := range str {
record[cha-'a']++
}
builder := make([]byte, 0)
for _, value := range record {
builder = append(builder, fmt.Sprintf("%d", value)...)
builder = append(builder, "_"...)
}
key := string(builder)
if _, ok := map0[key]; !ok {
map0[key] = make([]string, 0)
}
map0[key] = append(map0[key], str)
}
res := make([][]string, 0)
for _, list0 := range map0 {
res = append(res, list0)
}
return res
}
func groupAnagrams2(strs []string) [][]string {
map0 := make(map[string][]string)
for _, str := range strs {
chs := []byte(str)
sort.Slice(chs, func(i, j int) bool {
return chs[i] < chs[j]
})
key := string(chs)
if _, ok := map0[key]; !ok {
map0[key] = make([]string, 0)
}
map0[key] = append(map0[key], str)
}
res := make([][]string, 0)
for _, list0 := range map0 {
res = append(res, list0)
}
return res
}
执行结果如下: