49.给出一个字符串数组,实现一个算法给定一组字符串,将字母异位词组合在一起

本文主要是介绍49.给出一个字符串数组,实现一个算法给定一组字符串,将字母异位词组合在一起,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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")
}

这篇关于49.给出一个字符串数组,实现一个算法给定一组字符串,将字母异位词组合在一起的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092739

相关文章

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函