
Leetcode: Group Anagrams
发布日期:2025-04-05 03:39:31
浏览次数:9
分类:精选文章
本文共 2000 字,大约阅读时间需要 6 分钟。
举个例子,假设输入是["abc","cba","azyg","cba","cc","acb"],那么处理步骤是这样的:
将每个单词排序:
- "abc" 排序后变为 "abc"
- "cba" 排序后变为 "abc"
- "azyg" 排序后变为 "abyz"
- "cba" 排序后变为 "abc"
- "cc" 排序后变为 "cc"
- "acb" 排序后变为 "acb"
创建哈希表并将排序后的字符串作为键,将原始单词作为值存入对应的列表:
- "abc" 对应的列表包含["abc", "cba", "cba"]
- "abyz" 对应的列表包含["azyg"]
- "cc" 对应的列表包含["cc"]
- "acb" 对应的列表包含["acb"]
最后,对每个列表进行排序:
- "abc" 列表按字典序排列是 ["abc", "cba", "cba"](实际上因为重复的单词,会影响列表的排序,但这里示例中没有重复单词,只是为了描述)
- "abyz" 列表只有一个元素
- "cc" 列表只有一个元素
- "acb" 列表只有一个元素
最终返回所有包含多个单词的列表,用字典序排列:
[["abc", "cba", "cba"], ["abyz"], ["cc"], ["acb"]]
这就是完成任务的基本步骤,下面我将详细解析如何实现这个功能。整个代码思路是基于将每个单词排序后作为键,然后找到相同的键对应的所有单词,最后按照字典序返回这些单词列表。
代码解析
public class Solution { public List
> groupAnagrams(String[] strs) { List
> res = new ArrayList<>(); Map > map = new HashMap<>(); for (String item : strs) { char[] array = item.toCharArray(); Arrays.sort(array); String aftersort = new String(array); if (map.containsKey(aftersort)) { List list = map.get(aftersort); list.add(item); } else { List newlist = new ArrayList<>(); newlist.add(item); map.put(aftersort, newlist); } } for (List each : map.values()) { if (each.size() > 1) { Collections.sort(each); res.add(new ArrayList<>(each)); } } return res; }}
关键步骤解释:
初始化变量:
- 使用
List<List<String>> res
来保存最终的结果,每一组的单词按字典序排列。 - 使用
Map<String, List<String>> map
来存储相同排序后字符串对应的单词列表,键是排序后的字符串,值是List<String>
。
遍历输入字符串数组:对于每个输入的字符串item
,执行以下操作:
- 将
item
转换为字符数组char[] array
。 - 对字符数组进行排序。
- 将排序后的字符数组转换为字符串
aftersort
,作为关键。 - 检查
map
中是否存在aftersort
这个键,如果存在,将item
添加到对应的列表中;如果不存在,创建一个新的列表,将item
添加进去,并将这个列表放在map
中。
收集结果并排序:
- 遍历
map
中的每个值(即每个单词列表)。 - 如果列表中有超过一个元素,说明这些单词是变位词。
- 对该列表进行排序,以确保结果是按字典序排列的。
- 将排序后的列表加入到
res
中。
返回结果:返回res
,其中包含所有变位词分组后的结果,每一组都是按字典序排列。
注意事项:
- 处理空字符串:在排序和哈希表操作中,确保对空字符串正确处理。可以通过
Arrays.sort()
直接排序空字符数组,得到空字符串。 - 排序稳定性:字符串排序是稳定的,如果多个单词是完全相同的,会被正确归类到同一组中。
- 性能考虑:对于非常大的输入数组或长字符串,可能需要考虑优化排序方法或使用更高效的数据结构。
通过以上方法,可以高效地将给定的字符串数组按照变位词分组,并按字典序排列每一组中的单词,满足题目的要求。
发表评论
最新留言
感谢大佬
[***.8.128.20]2025年04月18日 18时13分26秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java基础学习总结(56)——学Java必知十大学习目标
2025-04-02
Java基础学习总结(57)——Jrebel插件热部署
2025-04-02
Java基础学习总结(59)——30 个java编程技巧
2025-04-02
Java基础学习总结(5)——多态
2025-04-02
Java基础学习总结(63)——Java集合总结
2025-04-02
Java基础学习总结(64)——Java内存管理
2025-04-02
Java基础学习总结(66)——配置管理库typesafe.config教程
2025-04-02
Java基础学习总结(67)——Java接口API中使用数组的缺陷
2025-04-02
Java基础学习总结(70)——开发Java项目常用的工具汇总
2025-04-02
Java基础学习总结(73)——Java最新面试题汇总
2025-04-02
Java基础学习总结(75)——Java反射机制及应用场景
2025-04-02
Java基础学习总结(76)——Java异常深入学习研究
2025-04-02
Java基础系列
2025-04-03
Kubernetes 自定义服务的启动顺序
2025-04-03
Kubernetes 资源调度详解
2025-04-03
Java基础:StringBuffer类概念、构造函数、常用方法
2025-04-03
Kubernetes 部署 kubeflow1.7.0
2025-04-03
Java基础:变量(声明、赋值、引用)、基本数据类型、作用域
2025-04-03
Java基础:如何编写并执行入门级别程序 Hello World
2025-04-03