LeetCode 49.字母异位词分组 (HashMap + 字符串排序)

class Solution { // 方法定义：返回双层字符串列表，存储所有异位词分组 public List<List<String>> groupAnagrams(String[] strs) { // 1.创建Map容器：key=排序字符串(分组标签)，value=原始单词列表(分组内容) Map<String, List<String>> map = new HashMap<>(); // 2.增强for遍历每一个原始单词 for(String str : strs) { // 3.字符串转字符数组：为排序做准备 char[] s = str.toCharArray(); // 4.字符数组排序：异位词排序后字符串一致 Arrays.sort(s); // 5.排序数组转回字符串，作为唯一分组key String key = new String(s); // 6.判断：当前分组已存在 if(map.containsKey(key)){ // 7.取出对应分组，加入当前原始单词 map.get(key).add(str); }else{ // 8.分组不存在：新建空列表 List<String> temp = new ArrayList<>(); // 9.将当前第一个单词加入新列表 temp.add(str); // 10.存入Map，完成新建分组 map.put(key, temp); } } // 11.取出所有分组，类型转换后返回结果 return new ArrayList<>(map.values()); } }

逐轮运行示例演示

• 第1轮 str = "eat" → 排序key="aet" → 无分组，新建列表 ["eat"] 存入map

• 第2轮 str = "tea" → 排序key="aet" → 分组存在，追加为 ["eat","tea"]

• 第3轮 str = "tan" → 排序key="ant" → 无分组，新建列表 ["tan"] 存入map

• 最终输出：[["eat","tea","ate"],["tan","nat"],["bat"]]

一、核心算法思路

• 利用 HashMap 键值对映射特性实现分组，整体时间复杂度接近 O(n logn)，为本题最优解法；

• 遍历每一个字符串，将字符串排序，排序后的字符串作为统一分组 key；

• key 不存在则新建分组列表，key 存在则将原字符串追加进对应分组；

• 遍历结束后取出 Map 所有 value，转为 List 集合返回，完成异位词分组。

前置基础：Map 底层基础定义

Map<K, V>

• K = Key（键）：用来查找的标识
• V = Value（值）：你想要保存的数据
• 判断规则：你打算拿什么东西当「查找标签」，K 就设为什么类型；你最终需要取出什么数据，V 就设为什么类型。
• 举例对照两道题： 1）两数之和：用数字找下标 →Map<Integer, Integer>2）字母异位词分组：用排序后的字符串找一组单词 →Map<String, List<String>>

（一）语法编译类错误（核心根源：Java 严格区分大小写）

1. HashMap 创建语法写错
   • 错误：Map<String, List<String>> map = new HashMap<>();
   • 标准固定语法：Map<K,V> 变量 = new HashMap<>();

（二）逻辑思路理解误区

1. 混淆 Map 的 key 与 value 存储内容
   • key：排序后的标准字符串（仅用来分组标记，不存入结果列表）
   • value：List<String>，存储原始异位单词
2. 分不清数组与 List 特性
   • String[]：长度固定，不能自动扩容；
   • ArrayList：动态列表，可无限.add()追加元素；
3. 不懂为什么最后要用new ArrayList<>(map.values())返回map.values()类型是Collection，和要求返回的List不兼容，必须通过 ArrayList 构造转换；

二、Java 专属工具方法积累

1. String 字符串方法

① str.toCharArray()

• 作用：将字符串拆分为char[]字符数组，字符串不可排序，只有字符数组能排序
• 用法：char[] 字符数组 = 字符串变量.toCharArray();

String str = "eat"; char[] arr = str.toCharArray(); // arr = {'e','a','t'}

② new String (char 数组)

• 作用：把排好序的 char 数组重新转回字符串，作为 HashMap 分组 key
• 用法：String key = new String(字符数组);

char[] arr = {'a','e','t'}; String key = new String(arr); // key = "aet"

2. Arrays 工具类（需导入import java.util.*;）

Arrays.sort (char [] 数组)

• 作用：对字符数组按字母 ASCII 升序排序，异位词排序后完全相同
• 用法：Arrays.sort(字符数组);

char[] arr = {'t','e','a'}; Arrays.sort(arr); // 排序后 {'a','e','t'}

3. List / ArrayList 方法

① new ArrayList<>()

• 作用：创建空的动态字符串列表
• 标准语法：List<String> 变量名 = new ArrayList<>();

② list.add (元素)

• 作用：向列表尾部追加元素，自动扩容

4. HashMap 核心三方法（解题高频）

① map.get(key)

• 作用：根据 key 取出对应的 value，仅支持 1 个参数
• 用法：List<String> group = map.get(key);

② map.put(key, value)

• 作用：向哈希表存入一组键值对，key 重复会覆盖旧 value
• 本题用法：map.put(排序字符串, 分组列表);

5. map.values()

• 作用：获取 Map 中所有 value，返回Collection集合，不含 key
• 场景：最后统一取出所有分组用于返回结果

三、通用固定模板积累

1. 创建 HashMap 模板Map<K类型,V类型> map = new HashMap<>();
2. 创建字符串列表模板List<String> list = new ArrayList<>();
3. 字符串排序转 key 完整固定流程

char[] arr = str.toCharArray(); Arrays.sort(arr); String key = new String(arr);

1. Map 分组结果返回模板return new ArrayList<>(map.values());

   ---