leetcode hot100【LeetCode 49. 字母异位词分组】java实现
LeetCode 49. 字母异位词分组
题目描述
给定一个字符串数组 strs
,请你将所有的字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例 1:
输入:strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:[["ate","eat","tea"],["nat","tan"],["bat"]
]
示例 2:
输入:strs = [""]
输出:[[""]]
示例 3:
输入:strs = ["a"]
输出:[["a"]]
提示:
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i]
仅包含小写字母
Java 实现解法
方法一:使用 HashMap 存储排序后的字符串
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {// 将字符串按字母顺序排序char[] chars = str.toCharArray();Arrays.sort(chars);String key = new String(chars);// 根据排序后的字符串作为键存储异位词map.putIfAbsent(key, new ArrayList<>());map.get(key).add(str);}return new ArrayList<>(map.values());}
}
解题思路
- 使用 HashMap:创建一个 HashMap,键为排序后的字符串,值为原始字符串的列表。
- 排序:对于每个字符串,将其转换为字符数组,进行排序,然后转换回字符串作为 HashMap 的键。
- 存储:如果 HashMap 中已经存在该键,则将原始字符串添加到对应的列表中;如果不存在,则创建一个新的列表,并将原始字符串添加到列表中,然后将键值对存入 HashMap。
- 返回结果:最后,将 HashMap 中的所有值(即所有字母异位词的列表)添加到一个新的列表中,并返回这个列表。
这种方法的时间复杂度是 O(n * k * log(k))
,其中 n
是字符串数组的长度,k
是字符串的最大长度。空间复杂度是 O(n * k)
,因为我们需要存储所有字符串的排序副本以及原始字符串的列表。
注意:此解法在实际应用中可能需要考虑字符串长度较大的情况,此时排序操作可能会影响性能。在某些情况下,可能需要考虑更高效的算法或数据结构。
注:题目来源leetcode网站