宁夏回族自治区网站建设_网站建设公司_ASP.NET_seo优化

大家好，今天深度拆解力扣中等题「字母异位词分组」的两种核心解法 ——排序法（简洁易实现）和计数法（高效优化版），并对比两者的适用场景，帮你彻底掌握这道经典题！

一、题目回顾

给定一个字符串数组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），追求极致时间效率。

五、两种方案对比总结