49.字母异位词分组
49. 字母异位词分组
鲁迅曾逼逼：老虎说草原是绿色的，驴子说草原是蓝色的，两人争论不休，于是
就找到狮子法官理论，结果狮子判老虎禁闭三天好好反思一下，因为他把时间浪
费在了一件毫无意义的事情上。这件事的寓意其实很朴素，不要争论，如果别人
觉得自己是对的，那你就对对对三连。把时间真正用到有意义的事情上，比如刷
二哥的 LeetCode 题解。
题意
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰
好只用一次。
难度
中等
示例
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
分析
这道题的重点是理解什么是字母异位词，简单点说，就是每个字母出的次数都一样的字符
串。
也就是说，如果两个字符互为 字母异位词，那么分别对它们进行排序后，必然是两个相
同的字符串。
我们可以借助这一特性，将每个字符串按照字符排序后作为哈希表的键，然后将相同键的
字符串归为一组。
如果看过 HashMap 的源码，其实就能找到类似的感觉，哈希相同的时候会使用拉链法将
key 相同的归为一组，放在链表中。
1. 初始化一个哈希表 map，其中键是排序后的字符串，值是对应的异位词列表
（ArrayList）。
2. 遍历输入数组中的每一个字符串，对字符串中的字符进行排序，然后将排序后的字符
串作为键，将原始字符串添加到该键对应的列表中。
3. 遍历完成后，哈希表中的每个键对应的值就是一个字母异位词组。
4. 返回哈希表中的所有值（即字母异位词分组）。
来看题解：
import java.util.*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 创建哈希表，键是排序后的字符串，值是异位词列表
Map<String, List<String>> map = new HashMap<>();
// 遍历每一个字符串
for (String str : strs) {
// 将字符串转换为字符数组并排序
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortedStr = new String(charArray); // 将排序后的字符数组转回字符串
// 将排序后的字符串作为键，原始字符串添加到对应的列表中
if (!map.containsKey(sortedStr)) {
map.put(sortedStr, new ArrayList<>());
}
map.get(sortedStr).add(str); // 添加异位词到列表中
}
// 返回哈希表中的所有值，即所有异位词分组
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
Solution solution = new Solution();
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> result = solution.groupAnagrams(strs);
System.out.println(result); // 输出 [["eat","tea","ate"], ["tan","nat"], ["bat"]]
}
}
其中 str.toCharArray() 可以将字符串转换为字符数组，Arrays.sort(charArray) 可以对
字符数组进行排序，new String(charArray) 可以将字符数组重新转换为字符串。
map.containsKey(sortedStr) 可以判断哈希表中是否包含某个键，map.put(sortedStr,
new ArrayList<>()) 可以将一个空的 ArrayList 添加到哈希表中，
map.get(sortedStr).add(str) 可以将异位词添加到相同 key 的列表中。
map.values() 可以获取哈希表中的所有值，返回类型是 Collection，我们可以通过 new
ArrayList<>(map.values()) 将其转换为 ArrayList。
049.字母异位词分组-20240920093520.png
整体题解的难度不大，主要是理解字母异位词的概念，以及如何利用哈希表来存储异位词
分组。
假设输入为 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]，处理过程如下：
1. eat 排序后为 aet，创建一个键为 aet 的列表，加入 eat。
2. tea 排序后为 aet，aet 键已存在，将 tea 加入该列表。
3. tan 排序后为 ant，创建一个键为 ant 的列表，加入 tan。
4. ate 排序后为 aet，将 ate 加入 aet 列表。
5. nat 排序后为 ant，将 nat 加入 ant 列表。
6. bat 排序后为 abt，创建一个键为 abt 的列表，加入 bat。
好，来看一下题解效率，还不错，击败 98.63 的用户。
049.字母异位词分组-20240920092959.png
总结
Java 在刷题的时候，比很多原生的编程语言，如 C 和 C++ 要容易一些，因为 Java 的 JDK
封装了很多有用的类库，包括 HashMap、ArrayList、Arrays 等，这些类库可以帮助我们
更快地完成题目。
前提条件是一定要掌握 Java 的这些基础类库，推荐阅读：
• HashMap 源码解析
• ArrayList 源码解析
• Arrays 源码解析
• String 类的其他方法
力扣链接：https://leetcode.cn/problems/group-anagrams/
