大家好，今天深度拆解力扣中等题「字母异位词分组」的两种核心解法 ——排序法（简洁易实现）和计数法（高效优化版），并对比两者的适用场景，帮你彻底掌握这道经典题！
一、题目回顾
给定一个字符串数组strs，将字母异位词（字母种类 / 数量相同、排列不同的字符串）分组，返回所有分组后的列表。
- 示例：输入
["eat","tea","tan","ate","nat","bat"]→ 输出[["eat","tea","ate"],["tan","nat"],["bat"]]。
二、核心思路：给异位词 “打标签”
字母异位词的核心特征是「字符组成完全相同」，因此只要能给每组异位词生成唯一的标签（key），就能用哈希表实现分组。两种解法的本质都是 “生成唯一 key + 哈希表分组”，区别仅在于「生成 key 的方式」。
三、方案 1：排序法（简洁易上手）
1. 核心逻辑
将每个字符串的字符排序，异位词排序后会得到相同的字符串（如eat/tea排序后都是aet），以此作为哈希表的 key。
2. 代码实现
import java.util.*; class Solution { // 排序法：简洁易实现，适合字符串较短的场景 public List<List<String>> groupAnagrams(String[] strs) { // key：排序后的字符串；value：对应异位词列表 Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { // 1. 字符数组排序，生成唯一key char[] chars = str.toCharArray(); Arrays.sort(chars); String key = new String(chars); // 2. 哈希表分组：无则新建列表，有则直接添加 List<String> list = map.getOrDefault(key, new ArrayList<>()); list.add(str); map.put(key, list); } // 3. 提取所有分组结果 return new ArrayList<>(map.values()); } }3. 复杂度分析
- 时间复杂度：
O(n×k log k)n= 字符串数量，k= 字符串最大长度；排序单字符串的时间是O(k log k)，遍历 + 排序整体为O(n×k log k)。 - 空间复杂度：
O(n×k)（存储哈希表的键和所有字符串）。
4. 适用场景
字符串长度k较小（如 k≤20），追求代码简洁性，无需极致性能。
四、方案 2：计数法（高效优化版）
1. 核心逻辑
排序法的瓶颈在 “字符排序”，计数法直接统计每个字符串中 26 个字母的出现次数（如eat的计数为a:1, e:1, t:1），将计数结果拼接成唯一 key，把单字符串处理时间从O(k log k)降至O(k)。
2. 代码实现
import java.util.*; class Solution { // 计数法：时间优化版，适合字符串较长的场景 public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { // 1. 初始化26字母计数数组（a-z对应下标0-25） int[] count = new int[26]; // 2. 统计每个字符出现次数 for (char c : str.toCharArray()) { count[c - 'a']++; // 'a'→0，'b'→1，以此类推 } // 3. 生成唯一key（用逗号分隔避免数字歧义，如11和1+1） StringBuilder sb = new StringBuilder(); for (int num : count) { sb.append(num).append(","); } String key = sb.toString(); // 4. 哈希表分组（逻辑同排序法） List<String> list = map.getOrDefault(key, new ArrayList<>()); list.add(str); map.put(key, list); } return new ArrayList<>(map.values()); } }3. 关键优化点
- 计数数组替代排序：仅遍历字符串一次（
O(k)），避免排序的O(k log k)开销； - 逗号分隔生成 key：防止 “计数 1 + 计数 1” 拼接成 “11”，与 “计数 11” 混淆（如
"aa"和"k"的计数直接拼接会都是2，加逗号后为2,0,...和0,...1,...，可区分）。
4. 复杂度分析
- 时间复杂度：
O(n×k)（仅遍历字符串和计数数组，无排序开销）； - 空间复杂度：
O(n×k)（额外占用计数数组，但可忽略，整体仍为O(n×k)）。
5. 适用场景
字符串长度k较大（如 k≥100），追求极致时间效率。
五、两种方案对比总结
| 解法 | 时间复杂度 | 空间复杂度 | 代码简洁度 | 适用场景 |
|---|---|---|---|---|
| 排序法 | O(n×k log k) | O(n×k) | 高 | 字符串短、追求代码简洁 |
| 计数法 | O(n×k) | O(n×k) | 中 | 字符串长、追求时间效率 |
