网站程序授权码设计类专业前景

49. Group Anagrams

题目

给定一组字符串，将字母异位词组合在一起。

示例:

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

注意:

• 所有输入均为小写字母。
• 输出的顺序可以是任意的。

解题思路

这道题可以将每个字符串都排序，排序完成以后，相同 Anagrams 的字符串必然排序结果一样。把排序以后的字符串当做 key 存入到 map 中。遍历数组以后，就能得到一个 map，key 是排序以后的字符串，value 对应的是这个排序字符串以后的 Anagrams 字符串集合。最后再将这些 value 对应的字符串数组输出即可。

代码实现

//代码实现思路:
//将字符串数组中的每个字符串转化为字符切片，并对其进行排序。
//使用一个字典（map）记录排序后的字符串作为键，原始字符串列表作为值，以实现分组。
//最后将字典中的所有值（即分组后的异位词）收集到结果中返回。
package leetcodeimport "sort"// 定义一个新的类型 sortRunes，该类型实现了 sort.Interface 接口，用于排序字符切片
type sortRunes []rune// Less 比较两个字符的大小
func (s sortRunes) Less(i, j int) bool {return s[i] < s[j]
}// Swap 交换两个字符的位置
func (s sortRunes) Swap(i, j int) {s[i], s[j] = s[j], s[i]
}// Len 返回字符切片的长度
func (s sortRunes) Len() int {return len(s)
}// groupAnagrams 函数将输入字符串数组中的字母异位词分组
func groupAnagrams(strs []string) [][]string {record := map[string][]string{} // 记录排序后的字符串与其对应的字母异位词组res := [][]string{}             // 最终结果// 遍历每个字符串for _, str := range strs {sByte := []rune(str)           // 将字符串转换为字符切片sort.Sort(sortRunes(sByte))    // 对字符切片进行排序sstrs := record[string(sByte)] // 获取排序后的字符串对应的异位词组sstrs = append(sstrs, str)     // 将原字符串加入到对应的异位词组中record[string(sByte)] = sstrs  // 更新记录}// 将所有的字母异位词组加入到结果中for _, v := range record {res = append(res, v)}return res
}

性能分析:

• 时间复杂度:
  对每个字符串排序的时间复杂度为 O(K log K)，其中 K 是字符串的最大长度。假设有 N 个字符串，那么总的时间复杂度为 O(N * K log K)。
• 空间复杂度:
  空间复杂度为 O(N * K)，其中 N 是字符串的数量，K 是字符串的最大长度。空间开销主要用于存储映射关系和最终的结果。

测试代码

package leetcodeimport ("fmt""testing"
)type question49 struct {para49ans49
}// para 是参数
// one 代表第一个参数
type para49 struct {one []string
}// ans 是答案
// one 代表第一个答案
type ans49 struct {one [][]string
}func Test_Problem49(t *testing.T) {qs := []question49{{para49{[]string{"eat", "tea", "tan", "ate", "nat", "bat"}},ans49{[][]string{{"ate", "eat", "tea"}, {"nat", "tan"}, {"bat"}}},},}fmt.Printf("------------------------Leetcode Problem 49------------------------\n")for _, q := range qs {_, p := q.ans49, q.para49fmt.Printf("【input】:%v       【output】:%v\n", p, groupAnagrams(p.one))}fmt.Printf("\n\n\n")
}