Java详解LeetCode 热题 100(02):LeetCode 49. 字母异位词分组（Group Anagrams）详解

1. 题目描述

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

2. 理解题目

这道题要求我们把字母异位词分到同一组。字母异位词是指两个单词包含相同的字母，但是字母的排列顺序不同。例如，"eat"和"tea"就是字母异位词，因为它们都由字母’e’、‘a’、't’组成。

关键点：

1. 字母异位词包含相同的字母，只是排列顺序不同
2. 我们需要将所有字母异位词放到同一组
3. 输出可以按任意顺序

3. 解法一：排序法

3.1 思路

最直观的方法是对字符串进行排序。字母异位词排序后会得到相同的字符串，我们可以将排序后的字符串作为键，原字符串作为值，存入哈希表中。

具体步骤：

1. 创建一个哈希表，键为排序后的字符串，值为字母异位词列表
2. 遍历输入数组中的每个字符串
3. 将当前字符串排序，得到排序后的字符串
4. 如果哈希表中已有该排序后的字符串作为键，则将当前字符串添加到对应值的列表中
5. 否则，在哈希表中创建一个新的键值对
6. 最后，返回哈希表的所有值，即为分组结果

3.2 Java代码实现

import java.util.*;public class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 特殊情况处理if (strs == null || strs.length == 0) {return new ArrayList<>();}// 创建哈希表，键为排序后的字符串，值为原字符串列表Map<String, List<String>> map = new HashMap<>();// 遍历所有字符串for (String str : strs) {// 将字符串转换为字符数组并排序char[] chars = str.toCharArray();Arrays.sort(chars);String sortedStr = new String(chars);// 如果哈希表中没有这个排序后的字符串，创建一个新列表if (!map.containsKey(sortedStr)) {map.put(sortedStr, new ArrayList<>());}// 将原字符串添加到对应列表中map.get(sortedStr).add(str);}// 返回哈希表的所有值return new ArrayList<>(map.values());}
}

3.3 代码详解

1. 首先检查输入是否为空，如果是，返回空列表
2. 创建一个HashMap，键是排序后的字符串，值是原字符串的列表
3. 遍历输入数组中的每个字符串：
   • 将字符串转换为字符数组，便于排序
   • 对字符数组进行排序
   • 将排序后的字符数组转换回字符串，作为键
   • 检查哈希表中是否已有该键，如果没有，创建一个新的列表
   • 将原字符串添加到对应键的列表中
4. 最后，通过map.values()获取所有值（即所有分组），转换为List返回

3.4 复杂度分析

• 时间复杂度：O(n * k * log k)，其中n是输入数组的长度，k是字符串的最大长度
  • 遍历n个字符串需要O(n)
  • 对每个字符串排序需要O(k * log k)
  • 总体时间复杂度为O(n * k * log k)
• 空间复杂度：O(n * k)
  • 哈希表需要存储所有字符串，最坏情况下需要O(n * k)的空间

3.5 适用场景

排序法直观易懂，适用于大多数情况。当字符串长度不是很大时，这种方法效率较高。

4. 解法二：计数法

4.1 思路

由于题目限定只包含小写字母，我们可以用一个长度为26的数组来统计每个字符串中各个字母的出现次数。具有相同字母计数的字符串就是字母异位词。

具体步骤：

1. 创建一个哈希表，键为字符计数的字符串表示，值为原字符串列表
2. 遍历每个输入字符串，统计每个字母的出现次数
3. 将统计结果转化为一个唯一的字符串表示，例如#1#2#0#0...表示’a’出现1次，'b’出现2次，'c’和’d’都不出现…
4. 使用这个唯一表示作为键，将原字符串加入对应的列表
5. 返回哈希表的所有值

4.2 Java代码实现

import java.util.*;public class Solution {public List<List<String>> groupAnagrams(String[] strs) {if (strs == null || strs.length == 0) {return new ArrayList<>();}Map<String, List<String>> map = new HashMap<>();for (String str : strs) {// 创建一个长度为26的数组，表示26个小写字母int[] counts = new int[26];// 统计每个字母的出现次数for (char c : str.toCharArray()) {counts[c - 'a']++;}// 将计数数组转换为唯一的字符串表示StringBuilder sb = new