LeetCode 49. 字母异位词分组 | 从排序到计数的哈希表优化之路-洪萨配资

在 LeetCode 的字符串类题目中，「字母异位词分组」是一道经典的中等难度题，它不仅考察字符串处理的基础能力，更是对哈希表键值设计思路的深度检验。这道题的核心是找到字母异位词的共性特征，并通过这个特征实现分组。今天我们就从最直观的暴力思路出发，一步步拆解到时间复杂度更优的计数法，带你吃透这道题的解题逻辑～

📌 题目重述

给你一个由小写字母组成的字符串数组strs，要求把数组中字母异位词归为一组，最后以任意顺序返回分组后的列表。
这里的关键是理解字母异位词：两个字符串如果包含的字母完全相同，只是排列顺序不同，那它们就是字母异位词。比如eat和tea，都由e、a、t组成，只是顺序不一样，就属于一组；而bat没有对应的异位词，单独成组。
举个例子，输入["eat", "tea", "tan", "ate", "nat", "bat"]，输出就是[["bat"],["nat","tan"],["ate","eat","tea"]]。

🚶 阶梯思路拆解

第一步：暴力思路（两两对比）🥾

刚开始接触这道题，最直接的想法是检查每两个字符串是否为字母异位词，然后手动分组。这是暴力解法的核心逻辑，虽然容易理解，但效率极低。

💡 核心逻辑

初始化一个结果列表，用于存储最终的分组；
遍历数组中的每个字符串s：
- 如果s还未被分组，创建一个新的子列表，将s加入；
- 再遍历数组中剩下的字符串t，检查t是否与s是字母异位词，若是则加入同一个子列表，并标记t为已分组；
最终返回结果列表。

判断两个字符串是否为字母异位词的方法：将两个字符串排序后比较是否相等（比如eat排序后是aet，tea排序后也是aet，则为异位词）。

✅ 代码实现（Java）

importjava.util.*;publicclassSolution{publicList<List<String>>groupAnagrams(String[]strs){List<List<String>>result=newArrayList<>();boolean[]isGrouped=newboolean[strs.length];// 标记是否已分组for(inti=0;i<strs.length;i++){if(isGrouped[i])continue;// 跳过已分组的字符串List<String>group=newArrayList<>();group.add(strs[i]);isGrouped[i]=true;// 遍历剩余字符串，找异位词for(intj=i+1;j<strs.length;j++){if(!isGrouped[j]&&isAnagram(strs[i],strs[j])){group.add(strs[j]);isGrouped[j]=true;}}result.add(group);}returnresult;}// 判断两个字符串是否为字母异位词privatebooleanisAnagram(Strings,Stringt){if(s.length()!=t.length())returnfalse;char[]sArr=s.toCharArray();char[]tArr=t.toCharArray();Arrays.sort(sArr);Arrays.sort(tArr);returnArrays.equals(sArr,tArr);}}

⚙️ 复杂度分析

复杂度类型	计算结果	说明
时间复杂度	O(n² * k log k)	n 是数组长度，k 是字符串的最大长度。两层嵌套循环是 O (n²)，每次判断异位词的排序操作是 O (k log k)
空间复杂度	O(n)	除了结果存储，仅使用了`isGrouped`数组，空间为 O (n)

🚫 遇到的问题

暴力解法的效率问题非常突出：当数组长度n达到 10⁴ 时，n² 就是 10⁸ 次运算，再加上字符串排序的开销，必然会超时。问题的核心在于重复的异位词判断（比如判断eat和tea后，又会判断tea和ate），我们需要找到一种方式，让所有异位词能自动归组，避免重复比较。

第二步：排序 + 哈希表（优化思路）🗺️

既然字母异位词排序后是完全相同的字符串，那我们可以把排序后的字符串作为哈希表的键，对应的值存储该组的所有异位词。这样遍历一次数组就能完成分组，彻底解决重复比较的问题。

💡 核心逻辑

初始化一个HashMap，键为排序后的字符串，值为该组异位词的列表；
遍历数组中的每个字符串s：
- 对s进行排序，得到key；
- 如果key不在HashMap中，创建一个新的列表并放入HashMap；
- 将s添加到key对应的列表中；
遍历结束后，将HashMap中的所有值取出，即为最终的分组结果。

📊 图文演示（以 strs=[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] 为例）

（如图所示）我们一步步看 HashMap 的变化过程：

遍历eat：排序后为aet，HashMap 中无aet，创建列表["eat"]，存入{aet: ["eat"]}；
遍历tea：排序后为aet，HashMap 中有aet，将tea加入列表，变为{aet: ["eat", "tea"]}；
遍历tan：排序后为ant，HashMap 中无ant，创建列表["tan"]，存入{aet: [...], ant: ["tan"]}；
遍历ate：排序后为aet，加入列表，aet对应的列表变为["eat", "tea", "ate"]；
遍历nat：排序后为ant，加入列表，ant对应的列表变为["tan", "nat"]；
遍历bat：排序后为abt，创建列表["bat"]，最终 HashMap 为{aet: [...], ant: [...], abt: ["bat"]}；
取出 HashMap 的值，得到结果[["eat","tea","ate"], ["tan","nat"], ["bat"]]。

✅ 代码实现（Java）

importjava.util.*;publicclassSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Strings:strs){// 将字符串排序作为键char[]charArr=s.toCharArray();Arrays.sort(charArr);Stringkey=newString(charArr);// 不存在则创建新列表if(!map.containsKey(key)){map.put(key,newArrayList<>());}// 将当前字符串加入对应列表map.get(key).add(s);}// 将map的值转换为结果列表returnnewArrayList<>(map.values());}}

⚙️ 复杂度分析

复杂度类型	计算结果	说明
时间复杂度	O(n * k log k)	n 是数组长度，k 是字符串最大长度。遍历数组是 O (n)，每个字符串排序是 O (k log k)
空间复杂度	O(n * k)	HashMap 需要存储所有字符串，空间为 O (n * k)

✨ 优化亮点

这种方法将时间复杂度从 O (n² * k log k) 降到了 O (n * k log k)，在 n 较大时效率提升非常明显，也是这道题的常用解法。但它仍有优化空间：字符串排序的 O (k log k) 开销可以通过字符计数进一步降低。

第三步：计数 + 哈希表（最优解法）🔢

由于题目规定字符串仅包含小写字母（共 26 个），我们可以用一个长度为 26 的数组统计每个字符出现的次数，再将这个计数数组转换为唯一的键（比如拼接成字符串#1#0#0#...#1），这样就能避免排序的开销。

💡 核心逻辑

初始化一个HashMap，键为字符计数的拼接字符串，值为该组异位词的列表；
遍历数组中的每个字符串s：
- 创建长度为 26 的数组count，统计s中每个小写字母的出现次数（count[0]对应a，count[1]对应b，以此类推）；
- 将count数组拼接为字符串（如eat的计数数组是[1,0,0,0,1,0,...1]，拼接为#1#0#0#...#1），作为key；
- 如果key不在HashMap中，创建新列表；将s加入对应列表；
最终将HashMap的值转换为结果列表。

📊 图文演示（以 strs=[“eat”,“tea”] 为例）

（如图所示）计数法的键生成过程：

处理eat：
- e是第 4 个字母，count[4] +=1；a是第 0 个字母，count[0] +=1；t是第 19 个字母，count[19] +=1；
- 计数数组为[1,0,0,0,1,0,...,1]（仅展示关键位置），拼接为#1#0#0#0#1#...#1作为key；
处理tea：
- 统计后计数数组与eat完全相同，拼接的key也一致，因此被加入同一个列表。

✅ 代码实现（Java）

importjava.util.*;publicclassSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Strings:strs){int[]count=newint[26];// 统计26个小写字母的出现次数for(charc:s.toCharArray()){count[c-'a']++;// 'a'对应0，'b'对应1...}// 将计数数组转换为字符串作为键StringBuildersb=newStringBuilder();for(intnum:count){sb.append('#').append(num);// 用#分隔避免数字混淆（如1和10）}Stringkey=sb.toString();if(!map.containsKey(key)){map.put(key,newArrayList<>());}map.get(key).add(s);}returnnewArrayList<>(map.values());}}

⚙️ 复杂度分析

复杂度类型	计算结果	说明
时间复杂度	O(n * k)	n 是数组长度，k 是字符串最大长度。遍历数组是 O (n)，每个字符串的计数和拼接是 O (k)
空间复杂度	O(n * k)	HashMap 存储所有字符串，空间为 O (n * k)

✨ 优化亮点

这种方法彻底去掉了排序的 O (k log k) 开销，时间复杂度降到了线性的 O (n * k)，是这道题的最优解法。需要注意的是，拼接计数数组时要使用分隔符（如#），避免出现1和10拼接后混淆的情况（比如count=[1,10]和count=[11,0]，不加分隔符都会变成110）。