LeetCode（Hot.2）—— 49.字符异位词分组题解

Problem: 49. 字母异位词分组

字母异位词的定义是：两个单词的字母组成一样，但顺序可以不同，比如 eat、tea 和 ate 就是一个组的。

思路

将每个字符串按字母排序，把排序后的字符串作为 key，相同 key 的放在一个 list 中，最终将这些 list 返回。

解题过程

1. 核心思想：

   • 字母异位词排序后是相同的字符串。

   • 我们可以将每个字符串排序后，作为 map 的 key，原始字符串作为 value。

   • 如果多个字符串排序后结果一致，说明它们属于同一个“异位词”组。

2. 实现方式：

（1）使用一个 HashMap<String, List>：

• key：排序后的字符串（唯一标识一组异位词）。
• value：原始字符串组成的列表。

（2）遍历输入数组 strs：

• 每个字符串转为字符数组并排序。
• 把排序后的字符串作为 key，根据 key 获取已有的 list，没有则新建。
• 把原字符串添加到对应的 list 中。

（3）最后返回 map 中所有的 value（即每组异位词）。

复杂度

• 时间复杂度：O(n * k log k)

• • 是字符串个数
• • 是字符串最大长度（每次排序耗时 O(k log k)）

• 空间复杂度：O(n * k)

• • 用于存储结果列表和中间 map

Code

class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> map = new HashMap<>();for(String str : strs) {// 1. 将每个单词转成 char 数组，并且进行排序char[] temp = str.toCharArray();Arrays.sort(temp);String key = new String(temp);// 2. 排序后的值作为 key，原始值作为 List 集合中的 value。相同的 key 存在同一个 List<String> 中List<String> list = map.getOrDefault(key, new ArrayList<>());list.add(str);map.put(key, list);}return new ArrayList<>(map.values());}
}