DeepSeek专家 LeetCode 49. 字母异位词分组 Java实现

以下是 LeetCode 49. 字母异位词分组 的 Java 实现，采用 哈希表 + 排序 的方法。

思路

字母异位词排序后得到的字符串相同，因此可以将排序后的字符串作为哈希表的键，原始字符串作为值存入对应的列表。遍历所有字符串，最终哈希表中每个键对应的列表即为一组字母异位词。

代码

importjava.util.*;classSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Stringstr:strs){// 将字符串转为字符数组并排序，得到统一键char[]chars=str.toCharArray();Arrays.sort(chars);Stringkey=newString(chars);// 将原始字符串加入对应键的列表List<String>list=map.getOrDefault(key,newArrayList<>());list.add(str);map.put(key,list);}returnnewArrayList<>(map.values());}}

复杂度分析

· 时间复杂度：O(n * k log k)，其中 n 是字符串数量，k 是字符串的最大长度。每个字符串排序需要 O(k log k)，遍历所有字符串需要 O(n)。
· 空间复杂度：O(n * k)，哈希表存储所有字符串，排序过程中还需要临时字符数组。

补充说明

· 如果字符串长度很大，可以用 字符计数编码（如 a2b3c1）代替排序，将时间复杂度优化到 O(n * k)，但排序方法更直观且通常足够。
· map.values() 返回的是 Collection<List>，需要包装成 ArrayList 返回。