[toc]
leetcode 49. 字母異位詞分組.

題目描述

49. 字母異位詞分組

給你一個字符串數(shù)組，請你將 字母異位詞 組合在一起?？梢园慈我忭樞蚍祷亟Y果列表。

字母異位詞 是由重新排列源單詞的字母得到的一個新單詞，所有源單詞中的字母通常恰好只用一次。

示例 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. 找出相同的字符串的下標,從原字符串數(shù)組中取出放入一個字符串數(shù)組中,組成一個二維字符串數(shù)組

• 時間復雜度(O(n^2logn))
• 空間復雜度(O(n))

法2

計數(shù)+哈希表\

1. 建立一個[]map[byte]int數(shù)組,key為字母,value為出現(xiàn)的次數(shù),用于儲存匹配的字符串規(guī)則
2. 與一個[][]string其中行與map的位置相對應,,用于儲存返回結果

我們拿到一個字符串,就從map數(shù)組中找匹配自己的一個map,就是出現(xiàn)的字符與次數(shù)都相同即為異構,就將這個字符串儲存到對應的行中,

如果沒有就建立一個新的字符串匹配的map,并將該 字符串儲存到新的行的第一個[new][0]string

最后輸出這個字符串二維數(shù)組

• 時間復雜度(O(n^2))
• 空間復雜度(O(n))

執(zhí)行結果

法1

排序:

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, str := range strs {
        // 將字符串轉化為字符數(shù)組并排序
        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)
    }

    // 將分組后的結果轉化為二維字符串數(shù)組并返回
    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

執(zhí)行結果：
通過
顯示詳情
查看示例代碼
添加備注

執(zhí)行用時：
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 {
        // 使用計數(shù)排序將字符串轉化為字符計數(shù)數(shù)組
        count := make([]int, 26)
        for _, ch := range str {
            count[ch-'a']++
        }

        // 將字符計數(shù)數(shù)組轉化為字符串作為 key，將原字符串添加到對應的 value 列表中
        key := fmt.Sprint(count)
        groups[key] = append(groups[key], str)
    }

    // 將分組后的結果轉化為二維字符串數(shù)組并返回
    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

執(zhí)行結果：
通過
顯示詳情
查看示例代碼
添加備注

執(zhí)行用時：
48 ms
, 在所有 Go 提交中擊敗了
5.66%
的用戶
內存消耗：
7.9 MB
, 在所有 Go 提交中擊敗了
61.62%
的用戶
通過測試用例：
118 / 118
炫耀一下:

本文由mdnice多平臺發(fā)布