洛阳瀍河建设局网站,qq群推广网站免费,20个著名wordpress公司,修改网站域名49. Group Anagrams
题目
给定一组字符串#xff0c;将字母异位词组合在一起。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ]
注意:
所有输入均为小写字母。输出的顺序可以…49. Group Anagrams
题目
给定一组字符串将字母异位词组合在一起。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ]
注意:
所有输入均为小写字母。输出的顺序可以是任意的。
解题思路
这道题可以将每个字符串都排序排序完成以后相同 Anagrams 的字符串必然排序结果一样。把排序以后的字符串当做 key 存入到 map 中。遍历数组以后就能得到一个 mapkey 是排序以后的字符串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 (fmttesting
)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)
}
