NOTES · 学习笔记
字母异位词分组:排序当特征,哈希做分组
题目
题目:给你一个字符串数组 strs,将字母异位词组合在一起,可以按任意顺序返回结果列表。比如 strs = ["eat", "tea", "tan", "ate", "nat", "bat"],输出 [["bat"],["nat","tan"],["ate","eat","tea"]]。
看示例:strs 中没有字符串可以通过重新排列形成 "bat";"nat" 和 "tan" 是字母异位词,因为它们重新排列后可以形成彼此;"ate"、"eat"、"tea" 同理。
字母异位词的特点是:如果两个字符串包含的字母相同,那么将它们排序后得到的字符串一定相同。例如 "eat"、"tea"、"ate" 排序后都会得到 "aet",说明它们属于同一组。因此可以用 HashMap 保存分组关系,映射为:排序后的字符串特征 → 原字符串集合。
创建一个 map[string][]string——键是字符串(如 "aet"、"ant"、"abt"),值是字符串切片(如 ["eat","tea","ate"])。然后遍历字符串数组 strs:因为遍历的是下标 i,先把当前字符串转成字符切片 []byte 并排序;把排序结果转成字符串作为 key;将原字符串加进 key 对应的 value 里。最后遍历 HashMap 中所有的 value,把每一组加进结果数组,返回。
func groupAnagrams(strs []string) [][]string {
m := make(map[string][]string) // 定义一个HashMap,key(string) → value([]string)
for i := range strs { // 遍历整个strs,因为i是下标,所以定义一个chars
chars := []byte(strs[i]) // 我们要遍历的是元素,所以用切片,将遍历下标转为了元素
sort.Slice(chars, func(i, j int) bool { // 将元素进行排序
return chars[i] < chars[j] // 匿名函数声明按从小到大排序:
}) // bool告诉排序函数,i位置的元素是否应该排在j位置元素前面
key := string(chars) // 元素目前是切片形式,定义一个key将其强转
m[key] = append(m[key], strs[i]) // 最终输出的是strs中的元素,将strs保存进hashmap中
// 映射关系:排序后的字符串特征 -> 原来的字符串
}
result := [][]string{} // 定义一个二维字符串切片
for _, value := range m { // 遍历hashmap中的value
result = append(result, value)
}
return result
}时间复杂度:设 n 为字符串数组 strs 的长度,k 为字符串的平均长度。遍历 strs 需要 n 次;对每个字符串:转成 []byte 需要 O(k),字符切片排序需要 O(k log k),转成字符串存入 HashMap 需要 O(k)。排序的复杂度最高,处理一个字符串是 O(k log k),共 n 个字符串,所以总时间复杂度 O(n · k log k)。
空间复杂度:map[string][]string 需要存储所有字符串。n 个字符串、每个长度 k,空间 O(nk)。