[toc]
leetcode 49. 字母异位词分组.

题目描述

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

解题思路

法1

方法1:排序,

1. 对每一个单独的字符串进行排序,(效果:异构字符串就全部变成相同字符串,)
2. 找出相同的字符串的下标,从原字符串数组中取出放入一个字符串数组中,组成一个二维字符串数组

• 时间复杂度(O(n^2logn))
• 空间复杂度(O(n))

法2

计数+哈希表\

1. 建立一个[]map[byte]int数组,key为字母,value为出现的次数,用于储存匹配的字符串规则
2. 与一个[][]string其中行与map的位置相对应,,用于储存返回结果

我们拿到一个字符串,就从map数组中找匹配自己的一个map,就是出现的字符与次数都相同即为异构,就将这个字符串储存到对应的行中,

如果没有就建立一个新的字符串匹配的map,并将该 字符串储存到新的行的第一个[new][0]string

最后输出这个字符串二维数组

• 时间复杂度(O(n^2))
• 空间复杂度(O(n))

执行结果

法1

排序:

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, str := range strs {
        // 将字符串转化为字符数组并排序
        chars := []byte(str)
        sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
        sortedStr := string(chars)

        // 将排好序的字符串作为 key，将原字符串添加到对应的 value 列表中
        groups[sortedStr] = append(groups[sortedStr], str)
    }

    // 将分组后的结果转化为二维字符串数组并返回
    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

执行结果：
通过
显示详情
查看示例代码
添加备注

执行用时：
20 ms
, 在所有 Go 提交中击败了
82.36%
的用户
内存消耗：
7.6 MB
, 在所有 Go 提交中击败了
81.35%
的用户
通过测试用例：
118 / 118
炫耀一下:

法2

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, str := range strs {
        // 使用计数排序将字符串转化为字符计数数组
        count := make([]int, 26)
        for _, ch := range str {
            count[ch-'a']++
        }

        // 将字符计数数组转化为字符串作为 key，将原字符串添加到对应的 value 列表中
        key := fmt.Sprint(count)
        groups[key] = append(groups[key], str)
    }

    // 将分组后的结果转化为二维字符串数组并返回
    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

执行结果：
通过
显示详情
查看示例代码
添加备注

执行用时：
48 ms
, 在所有 Go 提交中击败了
5.66%
的用户
内存消耗：
7.9 MB
, 在所有 Go 提交中击败了
61.62%
的用户
通过测试用例：
118 / 118
炫耀一下:

本文由mdnice多平台发布