[LeetCode刷题]49.字母异位词分组（通俗易懂的java题解）
大家好，今天我们来解决一道LeetCode上的经典题目——字母异位词分组。这道题难度中等，但其实是很多面试中的常客。我会用最通俗易懂的方式，一步步带你理解并解决这个问题。
题目描述
题目链接：49. 字母异位词分组 - 力扣（LeetCode）
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成
"bat"。 - 字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。 - 字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
先理解什么是字母异位词？
简单来说，字母异位词就是字母相同，但顺序不同的单词。
比如：
- "eat"、"tea"、"ate" 这三个单词，虽然字母顺序不同，但都是由
a、e、t这三个字母组成的，所以它们是字母异位词 - "tan" 和 "nat" 都是由
a、n、t组成的，也是一组异位词 - "bat" 由
a、b、t组成，和其他单词都不相同，所以单独成一组
解题思路（核心思想）
这道题的关键是：如何判断两个单词是字母异位词？
有一个非常巧妙的方法：把单词的字母排序后作为这个单词的"特征"
为什么这样可行？
- "eat" 排序后 → "aet"
- "tea" 排序后 → "aet"
- "ate" 排序后 → "aet"
看到没？只要是字母异位词，排序后的结果一定相同！这个排序后的字符串就像是一个"指纹"，可以帮助我们识别所有异位词。
代码实现（详细注释版）
class Solution { public List<List<String>> groupAnagrams(String[] strs) { // 步骤1：创建一个"字典"，用来存放分组 // key：单词的"特征"（比如排序后的字符串） // value：所有具有相同特征的单词 HashMap<String, List<String>> map = new HashMap<>(); // 步骤2：遍历每一个单词 for (int i = 0; i < strs.length; i++) { String currentWord = strs[i]; // 当前单词 // 步骤3：找出当前单词的特征 char[] letters = currentWord.toCharArray(); // 拆成字母 Arrays.sort(letters); // 字母排序 String feature = new String(letters); // 排序后就是特征 // 步骤4：看这个特征是否已经存在 if (map.containsKey(feature)) { // 如果存在，拿到这个组，把当前单词放进去 List<String> group = map.get(feature); group.add(currentWord); } else { // 如果不存在，创建新组 List<String> newGroup = new ArrayList<>(); newGroup.add(currentWord); map.put(feature, newGroup); } } // 步骤5：把字典里的所有组取出来返回 List<List<String>> result = new ArrayList<>(); for (List<String> group : map.values()) { result.add(group); } return result; } }详细执行过程演示
让我们用题目中的例子，一步步看代码是如何执行的：
输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
第1步：处理 "eat"
- 当前单词：
"eat" - 排序后得到特征：
"aet" - map中还没有
"aet"，所以创建新列表 - map状态：
{"aet" → ["eat"]}
第2步：处理 "tea"
- 当前单词：
"tea" - 排序后得到特征：
"aet" - map中已有
"aet"，获取列表["eat"]，加入"tea" - map状态：
{"aet" → ["eat", "tea"]}
第3步：处理 "tan"
- 当前单词：
"tan" - 排序后得到特征：
"ant" - map中没有
"ant"，创建新列表 - map状态：
{"aet" → ["eat", "tea"], "ant" → ["tan"]}
第4步：处理 "ate"
- 当前单词：
"ate" - 排序后得到特征：
"aet" - map中已有
"aet"，获取列表["eat", "tea"]，加入"ate" - map状态：
{"aet" → ["eat", "tea", "ate"], "ant" → ["tan"]}
第5步：处理 "nat"
- 当前单词：
"nat" - 排序后得到特征：
"ant" - map中已有
"ant"，获取列表["tan"]，加入"nat" - map状态：
{"aet" → ["eat", "tea", "ate"], "ant" → ["tan", "nat"]}
第6步：处理 "bat"
- 当前单词：
"bat" - 排序后得到特征：
"abt" - map中没有
"abt"，创建新列表 - map状态：
{"aet" → ["eat", "tea", "ate"], "ant" → ["tan", "nat"], "abt" → ["bat"]}
最后：返回结果
- 取出map中所有的value（即三个列表）
- 返回：
[["eat","tea","ate"], ["tan","nat"], ["bat"]]
复杂度分析
- 时间复杂度：O(n × klogk)
- n 是字符串数组的长度
- k 是字符串的最大长度
- 需要对每个字符串排序，排序的时间复杂度是 O(klogk)
- 空间复杂度：O(n × k)
- 需要存储所有的字符串
总结与思考
- 核心技巧：通过排序把异位词转换成相同的特征字符串
- 数据结构选择：HashMap非常适合这种需要"根据特征分组"的场景
- 解题步骤：
- 遍历每个单词
- 排序得到特征
- 根据特征分组存储
- 返回所有分组
相关题目推荐
- 有效的字母异位词
- 找到字符串中所有字母异位词
- 字符串的排列
最后的话
这道题看似复杂，但掌握了"排序后作为特征"这个技巧后，就会变得非常简单。希望通过这篇文章，你已经完全理解了字母异位词分组的解法。如果还有不明白的地方，欢迎在评论区留言讨论！
如果这篇文章对你有帮助，别忘了点赞、收藏、关注哦！
你的支持是我持续分享的动力！
