七叶笔记 » golang编程 » 2021-09-25：给定一个字符串数组，将字母异位词组合在一起。可以

2021-09-25：给定一个字符串数组，将字母异位词组合在一起。可以

分类: golang编程 | 浏览: 307

2021-09-25：给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词指字母相同，但排列不同的字符串。示例 1:输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]，输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]。示例 2:输入: strs = [“”]，输出: [[“”]]。示例 3:输入: strs = [“a”]，输出: [[“a”]]。

福大大 答案2021-09-25：

自然智慧。

方法一：对字符串排序，放哈希表。

方法二：记字符串的字符个数，放哈希表。

这两种方法，本质都是一样的。

代码用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
}

执行结果如下：

***

[左神java代码](

相关文章