给定一个字符串数组 strs ,将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意:若两个字符串中每个字符出现的次数都相同,则称它们互为变位词。
示例 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] 仅包含小写字母
注意:本题与主站 49 题相同:
1、哈希辅助;时间复杂度O(n^2log(n)),空间复杂度O(n^2)
func groupAnagrams(strs []string) [][]string {
m := make(map[string]int)
res := make([][]string, 0)
for i := 0; i < len(strs); i++ {
arr := []byte(strs[i])
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j]
})
newStr := string(arr)
if _, ok := m[newStr]; ok {
res[m[newStr]] = append(res[m[newStr]], strs[i])
} else {
m[newStr] = len(res)
res = append(res, []string{strs[i]})
}
}
return res
}
2、哈希辅助;时间复杂度O(n^2),空间复杂度O(n^2)
func groupAnagrams(strs []string) [][]string {
m := make(map[[26]int]int)
res := make([][]string, 0)
for i := 0; i < len(strs); i++ {
arr := [26]int{}
for j := 0; j < len(strs[i]); j++ {
arr[strs[i][j]-'a']++
}
if _, ok := m[arr]; ok {
res[m[arr]] = append(res[m[arr]], strs[i])
} else {
m[arr] = len(res)
res = append(res, []string{strs[i]})
}
}
return res
}
Medium题目,题目同leetcode 49.字母异位词分组、面试题10.02.变位词组
页面更新:2024-05-18
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号