织梦音乐网站百度竞价广告

字母异位词分组，力扣第49题，看似是“找不同”的排列游戏，实则是哈希表与字符串处理的经典结合。这道题就像是一把钥匙，能帮你打开“如何高效归类数据”的算法大门。今天，我们就用 Java 带你用“排序魔法”轻松破解它！

---

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

---

解题思路：排序+哈希表，双剑合璧！

核心思想

字母异位词的本质是字符组成完全相同，只是顺序不同。
如果能将所有异位词映射到同一个标识，就能轻松分组。

魔法步骤

1. “字符排序”魔法：将每个字符串的字符排序，得到一个“标准形态”（例如 "eat" → "aet"）。

2. 哈希表映射：以“标准形态”为键，原字符串为值存入哈希表，自动完成分组。

3. 一键收割：最终取出哈希表的所有值，就是分组结果。

---

代码实现：简洁才是终极优雅！

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {// Step 1: 将字符串转为字符数组并排序，得到“标准形态”char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);// Step 2: 将当前字符串加入对应的分组列表List<String> list = map.getOrDefault(key, new ArrayList<>());list.add(str);map.put(key, list);}// Step 3: 收割所有分组结果return new ArrayList<>(map.values());}
}

代码逐行解析

• 字符排序魔法：Arrays.sort(array) 将字符串字符按字典序排列，确保异位词得到相同的键。

• 哈希表操作：

  • getOrDefault(key, new ArrayList<>())：若键存在，获取对应列表；否则新建空列表。

  • map.put(key, list)：更新哈希表，保证列表始终最新。

• 结果收割：map.values() 直接获取所有分组，转换为 ArrayList 返回。

---

复杂度分析

• 时间复杂度：O(n * k log k)

  • n 是字符串数量，k 是字符串最大长度。

  • 每个字符串需排序（O(k log k)），总时间 O(n * k log k)。

• 空间复杂度：O(n * k)

  • 哈希表存储所有字符串的副本。

---

进阶思考：不用排序，还能怎么玩？

除了排序法，还可以用字符计数法：

• 统计每个字符串中字符的出现次数，将计数结果（如 a1b0c2...）作为哈希表的键。

• 但代码稍复杂，且效率不一定更高（尤其当字符串较长时）。

为什么本题推荐排序法？

• 代码简洁直观，Java中字符串排序API非常高效。

• 对中等长度的字符串，排序法和计数法性能差异不大。

---

总结

字母异位词分组的解题精髓在于：

1. 找到同一类元素的唯一标识（排序后的字符串）。

2. 哈希表的灵活运用，将分类问题转化为键值映射。

掌握这道题，你不仅学会了如何“归类数据”，更重要的是理解了**“空间换时间”**这一经典算法思想。下次遇到类似问题（如分组、去重），不妨想想：能不能造一个“魔法键”来一键解决？