问题背景
字母异位词分组是字符串处理中的经典问题。所谓异位词（Anagram），是指由相同字母以不同顺序组成的单词，如 “listen” 和 “silent”、”triangle” 和 “integral”。在搜索引擎的自动补全、密码学中的字谜破解、以及生物信息学中的基因序列比对等场景中，异位词检测都扮演着重要角色。
本文将用Java实现将一组字符串按异位词关系进行分组的算法，深入讲解排序键法和字符频率计数法两种核心策略，并分析其时间空间复杂度差异。
问题描述
给定一个字符串数组，将字母异位词组合在一起，可以按任意顺序返回结果列表。
示例
- 输入：
["eat", "tea", "tan", "ate", "nat", "bat"] - 输出：
[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
核心思路
思路一：排序作为键
异位词排序后的字符串必然相同。例如 “eat” 和 “tea” 排序后都是 “aet”。因此可以将排序后的字符串作为哈希表的键，原始字符串作为值进行分组。
思路二：字符频率计数
异位词的每个字符出现次数完全相同。可以统计每个字符的出现次数，将频率数组编码为字符串作为键。例如 “eat” 的频次数组为 a:1, e:1, t:1，编码为 "1#1#...#1"。
思路三：质数乘积映射（数学方法）
为26个字母分配不同的质数，将单词映射为其字母对应质数的乘积。异位词的乘积必然相等。该方法利用算术基本定理保证唯一性。
Java完整实现
import java.util.*;
/**
* 字母异位词分组 - 哈希表的多策略实现
* 对应力扣第49题
*/
public class GroupAnagrams {
/**
* 解法一：排序作为哈希键
* 对每个字符串排序，排序结果相同的属于同一组
* 时间复杂度：O(n * k * log k) 空间复杂度：O(n * k)
* n为字符串数量，k为字符串最大长度
*/
public List<List<String>> groupAnagramsSortKey(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
// Map<排序后的字符串, 原始字符串列表>
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
// 将字符串转为字符数组并排序
char[] chars = str.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
// 放入对应分组
groups.computeIfAbsent(sorted, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
/**
* 解法二：字符频率计数作为哈希键
* 避免排序开销，时间复杂度更优
* 时间复杂度：O(n * k) 空间复杂度：O(n * k)
*/
public List<List<String>> groupAnagramsCountKey(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
// 统计字符频率
int[] count = new int[26];
for (char c : str.toCharArray()) {
count[c - 'a']++;
}
// 将频率数组编码为字符串键
// 使用#分隔确保唯一性，如 "1#2#0#...#1"
StringBuilder keyBuilder = new StringBuilder();
for (int i = 0; i < 26; i++) {
keyBuilder.append('#');
keyBuilder.append(count[i]);
}
String key = keyBuilder.toString();
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
/**
* 解法二优化：使用固定长度字符数组编码键
* 针对小写字母场景优化键的生成效率
*/
public List<List<String>> groupAnagramsCountKeyOptimized(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
int[] count = new int[26];
for (char c : str.toCharArray()) {
count[c - 'a']++;
}
// 使用字符数组直接构建键，避免StringBuilder开销
char[] keyChars = new char[26];
for (int i = 0; i < 26; i++) {
keyChars[i] = (char) (count[i] + '0'); // 假设频率不超过9
}
// 注意：这种方法在频率>9时不安全，仅作演示
// 实际生产环境应使用解法二的#分隔方案
String key = new String(keyChars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
/**
* 解法三：质数乘积映射
* 为26个字母分配不同质数，单词映射为质数乘积
* 时间复杂度：O(n * k) 空间复杂度：O(n * k)
* 注意：长单词可能导致整数溢出，实际使用需谨慎
*/
public List<List<String>> groupAnagramsPrimeKey(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
// 前26个质数对应26个小写字母
int[] primes = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101
};
Map<Long, List<String>> groups = new HashMap<>();
for (String str : strs) {
long product = 1;
for (char c : str.toCharArray()) {
product *= primes[c - 'a'];
}
groups.computeIfAbsent(product, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
/**
* 扩展：判断两个字符串是否为异位词
*/
public boolean isAnagram(String s, String t) {
if (s == null || t == null) return s == t;
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : t.toCharArray()) {
count[c - 'a']--;
if (count[c - 'a'] < 0) {
return false;
}
}
// 检查是否全部归零（可选，如果长度相等则一定归零）
for (int c : count) {
if (c != 0) return false;
}
return true;
}
/**
* 扩展：找出所有由同一组字母组成的最长子串组合
*/
public List<List<String>> groupAnagramsByLength(String[] strs) {
// 先按长度分组（异位词长度必然相等）
Map<Integer, List<String>> lengthGroups = new HashMap<>();
for (String str : strs) {
lengthGroups.computeIfAbsent(str.length(), k -> new ArrayList<>()).add(str);
}
// 对每个长度组内进行异位词分组
List<List<String>> result = new ArrayList<>();
for (List<String> sameLengthGroup : lengthGroups.values()) {
result.addAll(groupAnagramsSortKey(sameLengthGroup.toArray(new String[0])));
}
return result;
}
/**
* 扩展：查找最大的异位词组
*/
public List<String> findLargestAnagramGroup(String[] strs) {
List<List<String>> groups = groupAnagramsCountKey(strs);
List<String> largest = new ArrayList<>();
for (List<String> group : groups) {
if (group.size() > largest.size()) {
largest = group;
}
}
return largest;
}
/**
* 扩展：支持Unicode字符的异位词分组
*/
public List<List<String>> groupAnagramsUnicode(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
// 使用代码点处理Unicode字符
int[] codePoints = str.codePoints().sorted().toArray();
StringBuilder keyBuilder = new StringBuilder();
for (int cp : codePoints) {
keyBuilder.appendCodePoint(cp);
}
String key = keyBuilder.toString();
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
// ============ 测试入口 ============
public static void main(String[] args) {
GroupAnagrams solution = new GroupAnagrams();
String[] test1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
String[] test2 = {""};
String[] test3 = {"a"};
String[] test4 = {"listen", "silent", "enlist", "inlets", "google", "gogole"};
System.out.println("===== 异位词分组测试 =====");
System.out.println("\n测试1: " + Arrays.toString(test1));
System.out.println("排序键法: " + solution.groupAnagramsSortKey(test1));
System.out.println("频率计数法: " + solution.groupAnagramsCountKey(test1));
System.out.println("质数映射法: " + solution.groupAnagramsPrimeKey(test1));
System.out.println("\n测试2 (空串): " + Arrays.toString(test2));
System.out.println("结果: " + solution.groupAnagramsCountKey(test2));
System.out.println("\n测试3 (单字符): " + Arrays.toString(test3));
System.out.println("结果: " + solution.groupAnagramsCountKey(test3));
System.out.println("\n测试4: " + Arrays.toString(test4));
System.out.println("结果: " + solution.groupAnagramsCountKey(test4));
// 异位词判断测试
System.out.println("\n===== 异位词判断 =====");
System.out.println("listen vs silent: " + solution.isAnagram("listen", "silent"));
System.out.println("hello vs world: " + solution.isAnagram("hello", "world"));
// 最大分组测试
System.out.println("\n===== 最大异位词组 =====");
System.out.println("test4的最大组: " + solution.findLargestAnagramGroup(test4));
}
}
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 核心思想 | 适用场景 |
|---|---|---|---|---|
| 排序键法 | O(n·k·log k) | O(n·k) | 排序后比较 | 通用场景，代码简洁 |
| 频率计数法 | O(n·k) | O(n·k) | 字符频次统计 | 字符串较长时更优 |
| 质数映射法 | O(n·k) | O(n·k) | 质数乘积唯一性 | 理论优雅，注意溢出 |
| Unicode排序法 | O(n·k·log k) | O(n·k) | 代码点排序 | 多语言文本处理 |
其中n为字符串数量，k为字符串最大长度。
关键技巧详解
1. 哈希键设计
异位词分组的核心是找到一个不变量（Invariant）作为分组的依据：
– 排序后的字符串是不变量
– 字符频率分布是不变量
– 质数乘积（在数学意义上）是不变量
2. computeIfAbsent简化代码
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str) 是Java 8引入的优雅写法，避免了冗长的 containsKey 判断。
3. 频率计数键的编码
使用 # 分隔频率值是为了避免歧义。例如 "ab" 和 "ba" 的频率都是 {a:1, b:1}，编码为 "#1#1"。如果不使用分隔符， "1" 和 "11" 可能产生冲突。
4. 质数映射的数学原理
算术基本定理（唯一分解定理）保证每个大于1的整数都有唯一的质因数分解。因此不同字符组合的乘积必然不同。但实际编程中需注意整数溢出问题。
扩展应用
- 拼写检查器：利用异位词关系推荐可能的正确拼写
- 密码学字谜：快速查找给定字母能组成的所有有效单词
- 基因序列比对：DNA片段的异位词关系对应相同的碱基组成
- 社交媒体用户名推荐：输入用户名时推荐字母重新排列的可用变体
