字母异位分词-LeetCode49

数据小冰

发布于 2022-08-15 14:21:00

1620

发布于 2022-08-15 14:21:00

文章被收录于专栏：数据小冰

1.题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

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

说明：

•所有输入均为小写字母。
•不考虑答案输出的顺序。

2.我的题解

func groupAnagrams(strs []string) [][]string {
    m:=map[string][]string{}
    for _, str:=range strs{
        cs:=countString(str)
        m[cs]=append(m[cs],str)
      }

    ret:=make([][]string,0,len(m))
    for _, v:=range m{
        ret=append(ret,v)
    }
    return ret
 }


func countString(s string) string{
    count:=[26]int{}
    for _, r:=range []rune(s){
        index:=r-'a'
        if index<0 || index>=26{
            continue //exception filter it
        }
        count[index]+=1
    }
    var rs string
    for _, c:=range count{
        rs+=strconv.Itoa(c)
    }
    return rs
}

3.官方题解1

func groupAnagrams(strs []string) [][]string {
    mp := 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)
        mp[sortedStr] = append(mp[sortedStr], str)
    }
    ans := make([][]string, 0, len(mp))
    for _, v := range mp {
        ans = append(ans, v)
    }
    return ans
}

4.官方题解2

1.字符串s <==> int[26]等价   
2.map初始化方式 mp:=map[string][]string{}
3.map的key还可以是数组
func groupAnagrams(strs []string) [][]string {
    mp := map[[26]int][]string{}
    for _, str := range strs {
        cnt := [26]int{}
        for _, b := range str {
            cnt[b-'a']++
        }
        mp[cnt] = append(mp[cnt], str)
    }
    ans := make([][]string, 0, len(mp))
    for _, v := range mp {
        ans = append(ans, v)
    }
    return ans
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除

nat