49. 字母异位词分组
type
status
date
slug
summary
tags
category
difficulty
icon
password
49. 字母异位词分组
题目描述
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。
示例
示例 1:
示例 2:
示例 3:
提示
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]仅包含小写字母
解决方案
解题思路
这道题目要求我们将所有字母异位词组合在一起。字母异位词是指两个字符串中的字母出现次数完全相同，只是排列顺序不同。
方法：排序 + 哈希表
核心思路是：将每个字符串排序后作为哈希表的键，原字符串作为值存储。这样所有的字母异位词排序后都会得到相同的字符串，从而被分到同一组。
实现步骤
- 遍历输入的字符串数组
strs
- 对于每个字符串，创建其副本并对字符进行排序
- 使用排序后的字符串作为哈希表的键，将原字符串加入对应的值数组中
- 最后遍历哈希表，将所有值数组加入结果集
复杂度分析
时间复杂度：
- 遍历字符串数组需要 O(n) 的时间
- 对每个字符串排序需要 O(klogk) 的时间
- 总时间复杂度为 O(n * klogk)
空间复杂度：
需要一个哈希表来存储所有字符串，空间复杂度为 O(n * k)
代码详解
- 使用
unordered_map存储排序后的字符串到原字符串数组的映射：
- 遍历每个字符串，将其排序后作为键存储：
- 将哈希表中的所有值数组收集到结果数组中：
这种解法的优点是思路直观，实现简单。主要的时间消耗在字符串排序上。如果字符串长度较大，可以考虑使用计数方法来代替排序，即统计每个字符的出现次数作为哈希表的键。
- 作者:Episkey
- 链接:https://episkey.top/article/group-anagrams
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
