LeetCode49 字母异位词分组｜HashMap 分组，数组 toString 大坑

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词：字母组成完全一样，字符顺序不一样，例如eat、tea、ate。

我的做题思考全过程

审题：要把字母一样、顺序不一样的字符串分到同一组。
我想到一个关键点：异位词把字符排序之后，得到的字符串完全一样。

解题思路：

1. 使用 HashMap 做分组，key 存放排序后的字符串，value 存放一组原始字符串 List。
2. 循环遍历字符串数组，取出每一个字符串 s。
3. String 不能直接排序，转为 char [] 字符数组，调用 Arrays.sort 对数组排序。
4. 将排完序的字符数组转字符串，作为 map 的 key。
5. 判断 map 有没有这个 key：没有就新建一个 ArrayList 放进去；有就直接拿到已有的 List。
6. 把原始字符串 s 添加进 list。
7. 全部遍历结束，map 的所有 value 就是分组完成的数据，转为 List 返回。

做题踩坑记录（真实写代码遇到的错误）

1. ❗char 数组不能直接使用arr.toString()
   我写代码写成 String key = arr.toString;，直接编译报错；改成arr.toString()运行也不对。

char 数组调用 toString 得到的是内存地址[C@xxxx，不是字符串内容。
✅正确写法：new String(arr)，把 char 数组转为真正的字符串。

2. 不能new List<List<String>>[]
   Java 不支持直接 new 带泛型的数组，一开始想直接创建二维 List 数组存储分组，编译报错，改用 HashMap 分组才解决。
3. map.values () 不能直接 returnmap.values()返回的是 Collection 集合，和题目需要返回的List<List<String>>类型不匹配。
   ✅需要包装：new ArrayList<>(map.values())。
4. 空指针风险
   调用map.get(key).add(s)之前，必须containsKey判断 key 是否存在。
   如果 key 不存在，get 拿到 null，调用 add 直接抛出空指针异常。
5. for 循环两种写法
   可以用普通 for 下标循环，也可以增强 for 循环。本题我使用下标 for 循环，手动拿strs[i]。

AC 完整代码

import java.util.*;
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();
        for(int i = 0;i<strs.length;i++){
            String s=strs[i];
            char[] arr=s.toCharArray();
            Arrays.sort(arr);
            String key=new String(arr);
            if(!map.containsKey(key)){
                map.put(key,new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

• 时间复杂度：(O(n*k \log k)) n 是字符串数量，k 字符串最大长度
• 空间复杂度：(O(nk))

复习 HashMap 刷题常用 API

表格

总结

1. char [] 转字符串：new String(char数组)，千万不要直接数组.toString ()。
2. 分组类题目优先想到 HashMap，用一个特征值当 key 做归类。
3. get 之前优先 containsKey 判断，规避空指针。
4. Collection 不能直接当 List 返回，用new ArrayList<>(collection)做转换。