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

class Solution { // 方法定义返回双层字符串列表存储所有异位词分组 public ListListString groupAnagrams(String[] strs) { // 1.创建Map容器key排序字符串(分组标签)value原始单词列表(分组内容) MapString, ListString 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.分组不存在新建空列表 ListString temp new ArrayList(); // 9.将当前第一个单词加入新列表 temp.add(str); // 10.存入Map完成新建分组 map.put(key, temp); } } // 11.取出所有分组类型转换后返回结果 return new ArrayList(map.values()); } }逐轮运行示例演示第1轮 str eat → 排序keyaet → 无分组新建列表 [eat] 存入map第2轮 str tea → 排序keyaet → 分组存在追加为 [eat,tea]第3轮 str tan → 排序keyant → 无分组新建列表 [tan] 存入map最终输出[[eat,tea,ate],[tan,nat],[bat]]一、核心算法思路利用 HashMap 键值对映射特性实现分组整体时间复杂度接近 O(n logn)为本题最优解法遍历每一个字符串将字符串排序排序后的字符串作为统一分组 keykey 不存在则新建分组列表key 存在则将原字符串追加进对应分组遍历结束后取出 Map 所有 value转为 List 集合返回完成异位词分组。前置基础Map 底层基础定义MapK, VK Key键用来查找的标识V Value值你想要保存的数据判断规则你打算拿什么东西当「查找标签」K 就设为什么类型你最终需要取出什么数据V 就设为什么类型。举例对照两道题 1两数之和用数字找下标 →MapInteger, Integer2字母异位词分组用排序后的字符串找一组单词 →MapString, ListString一语法编译类错误核心根源Java 严格区分大小写HashMap 创建语法写错错误MapString, ListString map new HashMap();标准固定语法MapK,V 变量 new HashMap();二逻辑思路理解误区混淆 Map 的 key 与 value 存储内容key排序后的标准字符串仅用来分组标记不存入结果列表valueListString存储原始异位单词分不清数组与 List 特性String[]长度固定不能自动扩容ArrayList动态列表可无限.add()追加元素不懂为什么最后要用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 aet2. 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()作用创建空的动态字符串列表标准语法ListString 变量名 new ArrayList();② list.add (元素)作用向列表尾部追加元素自动扩容4. HashMap 核心三方法解题高频① map.get(key)作用根据 key 取出对应的 value仅支持 1 个参数用法ListString group map.get(key);② map.put(key, value)作用向哈希表存入一组键值对key 重复会覆盖旧 value本题用法map.put(排序字符串, 分组列表);5. map.values()作用获取 Map 中所有 value返回Collection集合不含 key场景最后统一取出所有分组用于返回结果三、通用固定模板积累创建 HashMap 模板MapK类型,V类型 map new HashMap();创建字符串列表模板ListString list new ArrayList();字符串排序转 key 完整固定流程char[] arr str.toCharArray(); Arrays.sort(arr); String key new String(arr);Map 分组结果返回模板return new ArrayList(map.values());