题目描述:给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]示例 2:
输入: strs = [""] 输出: [[""]]示例 3:
输入: strs = ["a"] 输出: [["a"]]提示:
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i]
仅包含小写字母
代码思路:
对于给定的字符串数组 strs
中的每个字符串 s
:
- 将字符串
s
转换为字符数组cs。
- 对字符数组
cs
进行排序,使得相同字母的字符串在排序后具有相同的字符顺序。 - 将排序后的字符数组
cs
转换为字符串key
,作为分组的键。 - 从哈希映射
temp
中获取键key
对应的值,如果键不存在则创建一个新的空列表。 - 将原始字符串
s
添加到对应分组的列表中。 - 更新哈希映射
temp
中键key
对应的值为更新后的列表。
使用了哈希映射来实现,只需要遍历一次字符串数组,将每个字符串排序后作为键存入哈希映射中,然后将属于同一组的字符串放入对应的值中,最后,将哈希映射中的所有值(即分组后的字符串列表)返回作为结果。
这个算法的时间复杂度为 O(n * mlogm),其中 n 是字符串数组的长度,m 是字符串的平均长度。因为需要对每个字符串进行排序,排序的时间复杂度是 O(mlogm)。而算法的空间复杂度为 O(n * m),主要是哈希映射和存储分组后的字符串列表所占用的空间。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> temp = new HashMap<>();
for (String s : strs) {
char[] cs = s.toCharArray();
Arrays.sort(cs);
String key = Arrays.toString(cs);
List<String> value = temp.getOrDefault(key, new LinkedList<>());
value.add(s);
temp.put(key, value);
}
return new LinkedList<>(temp.values());
}
}