JAVA高效分组变位词：无需排序的哈希映射方法
在处理字符串分组相关问题时，变位词分组是一个常见的场景。变位词指的是由相同字母重排列形成的字符串，比如 "eat"、"tea"、"ate" 就属于同一组变位词。传统的解法通常会先对字符串排序，将排序后的结果作为哈希表的键来分组，但排序本身会带来 O(k log k) 的时间开销（k 是字符串长度）。今天介绍一种无需排序的哈希映射方法，通过统计字符出现次数生成唯一键，效率更高。
核心思路
变位词的本质是组成字符串的字符种类和每个字符的出现次数完全一致。我们可以统计每个字符串中每个字符的出现次数，然后根据计数结果生成一个唯一的字符串作为哈希表的键：
- 遍历字符串的每个字符，统计 26 个小写字母的出现次数（如果是包含其他字符的场景可以扩展数组长度）
- 将计数结果拼接成固定格式的字符串，比如字符 a 出现 1 次，字符 e 出现 1 次，字符 t 出现 1 次，就生成 "#1#0#0#0#1#0...#1#0..." 这样的键
- 用这个键作为 HashMap 的 key，对应的 value 就是该组变位词组成的列表
- 最终遍历 HashMap 的 value 集合，就是所有分组后的结果
完整代码实现
下面是基于上述思路的 Java 实现代码，假设输入字符串仅包含小写字母，如果是其他场景可以调整计数数组的长度和键的生成逻辑：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AnagramGroup {
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']++;
}
// 根据计数结果生成唯一键，格式为 #次数#次数... 避免不同计数拼接后冲突
StringBuilder keyBuilder = new StringBuilder();
for (int num : count) {
keyBuilder.append('#').append(num);
}
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) {
AnagramGroup solution = new AnagramGroup();
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);
}
}
}复杂度分析
这种方法的效率优势非常明显：
- 时间复杂度：假设输入字符串数组长度为 n，每个字符串平均长度为 k，那么统计字符计数的时间是 O(n*k)，生成键的时间也是 O(n*k)，整体时间复杂度是 O(n*k)，比带排序的 O(n*k log k) 更优。
- 空间复杂度：需要存储哈希表和所有字符串，最坏情况下每个字符串都是独立的变位词组，空间复杂度是 O(n*k)，和排序方法的空间复杂度相当。
场景扩展
如果输入的字符串包含大写字母、数字或者其他特殊字符，只需要调整计数数组的长度即可。比如要支持 ASCII 字符，可以把数组长度设为 128，用字符的 ASCII 码作为索引；如果要支持 Unicode 字符，也可以改用 HashMap<Character, Integer> 来统计计数，生成键的时候遍历这个 HashMap 即可，逻辑和上述代码基本一致。