Java实现无排序分组同字母异位词：哈希映射与字符计数详解
在字符串处理场景中，我们经常需要将同字母异位词分组。同字母异位词指的是字母相同但排列顺序不同的单词，例如"eat"、"tea"、"ate"都属于同一组同字母异位词。常见的思路是先对单词排序，再用排序后的结果作为分组键，但排序操作会增加时间复杂度。本文将介绍一种无需排序，通过字符计数结合哈希映射实现分组的方法，时间复杂度更低，逻辑也更清晰。
核心思路解析
无需排序的核心逻辑是：每个单词的字母组成是固定的，我们可以统计每个单词中26个小写字母的出现次数，将这个计数结果作为该单词的唯一标识。因为同字母异位词的字母计数完全一致，所以可以用计数结果作为哈希映射的键，将对应的单词放到同一个分组中。
具体实现步骤如下：
- 遍历所有待分组的单词，对每个单词进行字符计数，统计26个小写字母的出现次数
- 将计数结果转换为可哈希的字符串形式，作为当前单词的分组键
- 使用哈希映射存储键到对应单词列表的映射关系，如果键已存在就将单词加入对应的列表，不存在则新建列表
- 最后将哈希映射中的所有值（即分组后的单词列表）收集起来返回
完整代码实现
下面是完整的Java实现代码，包含详细的注释说明每一步的逻辑：
import java.util.*;
public class GroupAnagrams {
public List<List<String>> groupAnagrams(String[] strs) {
// 哈希映射：键为计数结果字符串，值为同字母异位词组成的列表
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
// 统计26个小写字母的出现次数
int[] count = new int[26];
for (char c : str.toCharArray()) {
count[c - 'a']++;
}
// 将计数数组转换为字符串作为键，格式为"次数1#次数2#...#次数26"
StringBuilder keyBuilder = new StringBuilder();
for (int i = 0; i < 26; i++) {
keyBuilder.append(count[i]).append("#");
}
String key = keyBuilder.toString();
// 如果键不存在，新建列表并放入映射
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
// 将当前单词加入对应的分组列表
map.get(key).add(str);
}
// 返回所有分组结果
return new ArrayList<>(map.values());
}
// 测试示例
public static void main(String[] args) {
GroupAnagrams solution = new GroupAnagrams();
String[] testStrs = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> result = solution.groupAnagrams(testStrs);
System.out.println("分组结果：");
for (List<String> group : result) {
System.out.println(group);
}
}
}代码逻辑说明
上述代码中，我们首先创建了一个HashMap用来存储分组映射。遍历每个输入的单词时，先初始化一个长度为26的int数组，用来记录每个字母的出现次数：因为单词只包含小写字母，所以字符c减去'a'就能得到对应的数组下标，对应位置的次数加1。
接下来需要将计数数组转换为字符串作为哈希键。这里采用"次数#次数#..."的格式，比如单词"eat"的计数数组中，e（下标4）对应1，a（下标0）对应1，t（下标19）对应1，其余都是0，转换后的键就是"1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#"，只要是两个同字母异位词，得到的这个键一定完全相同。
之后检查哈希映射中是否已经存在这个键，如果不存在就新建一个空列表放入映射，再把当前单词加入对应的列表。最后只需要把映射中的所有值收集起来，就是最终的分组结果。
复杂度分析
假设输入数组长度为n，每个单词的平均长度为k：
- 时间复杂度：遍历所有单词需要O(n)，每个单词统计字符需要O(k)，转换键需要O(26)也就是常数时间，所以整体时间复杂度是O(n*k)
- 空间复杂度：哈希映射需要存储所有的单词，所以空间复杂度是O(n*k)，用来存放所有单词的字符串
对比先排序再分组的O(n*k log k)时间复杂度，这种方法在处理较长单词时性能优势会更明显，同时避免了排序操作带来的额外开销。
边界情况处理
实际使用中还需要考虑一些边界场景：
- 如果输入数组为空，方法会直接返回空的列表集合，不会出现空指针异常
- 如果单词包含大写字母或其他字符，上述代码只处理小写字母的情况，实际使用时可以根据需求扩展计数数组的长度，比如扩展到128位处理ASCII字符，或者增加大小写转换的逻辑
- 如果输入的单词有重复，比如两个相同的"eat"，它们会被分到同一个分组中，符合预期的分组逻辑
这种方式不需要对单词本身做任何修改，也不依赖排序操作，逻辑直观且效率稳定，适合大多数同字母异位词分组的场景。
Java同字母异位词分组字符计数哈希映射无排序算法字符串处理修改时间：2026-05-24 12:23:43