leetcode 49. 字母异位词分组

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 炫耀一下: