LeetCode无排序分组变位词：基于字符频率的Java实现与复杂度分析
在日常的算法练习中，变位词分组是LeetCode上的经典题目，传统解法通常会先对每个字符串排序，再用排序后的字符串作为键分组。但如果我们遇到题目要求不能对字符串排序的场景，基于字符频率的统计方式就是更合适的选择。本文将介绍这种无排序的分组实现方案，同时分析其时间和空间复杂度。
问题背景
变位词指的是字母相同、但排列顺序不同的字符串，比如"eat"、"tea"、"ate"就属于同一组变位词。题目要求我们输入一个字符串数组，将所有的变位词分到同一组，最终返回分组后的结果。
传统排序解法的核心是对每个字符串的字符排序，排序后的字符串作为哈希表的键，相同键的字符串归入同一组。而如果不允许排序，我们就需要找到一种不依赖顺序的方式，来描述字符串的字符组成特征，字符频率统计就是最直观的思路。
核心实现思路
每个字符串的字符频率可以通过长度为26的数组来记录（假设只包含小写字母），数组的每个位置对应一个字母，值就是该字母出现的次数。两个字符串如果是变位词，那么它们的字符频率数组一定完全相同。因此我们可以把频率数组转换成唯一的字符串作为哈希表的键，这样就不需要对原字符串排序，也能完成分组。
具体实现步骤如下：
- 遍历输入的字符串数组，对每个字符串统计字符频率
- 将频率数组转换为固定格式的字符串，比如"1#2#0#..."，每个数字对应一个字母的出现次数，用特殊字符分隔避免歧义
- 以频率字符串为键，将当前字符串添加到对应键的分组列表中
- 最终遍历哈希表，收集所有分组结果返回
Java代码实现
下面是完整的Java实现代码，包含了详细的注释说明每一步的逻辑：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class GroupAnagrams {
public List<List<String>> groupAnagrams(String[] strs) {
// 哈希表，键是字符频率转换后的字符串，值是同一组的变位词列表
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
// 长度为26的数组，记录每个小写字母的出现次数
int[] freq = new int[26];
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// 计算字符对应的数组下标，'a'对应0，'z'对应25
freq[c - 'a']++;
}
// 将频率数组转换为唯一标识的字符串，用#分隔避免不同频率组合产生相同字符串
StringBuilder keyBuilder = new StringBuilder();
for (int i = 0; i < 26; i++) {
keyBuilder.append(freq[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());
}
}上面的代码中，我们用StringBuilder拼接频率字符串，每个频率后面加一个#分隔，这样可以避免类似[2,3]和[23]这样的不同频率数组生成相同的字符串。比如频率数组是[1,2,0,...]，生成的键就是"1#2#0#..."，唯一对应这组字符频率。
复杂度分析
我们可以从时间和空间两个维度分析这个实现的性能：
- 时间复杂度：假设输入数组有n个字符串，每个字符串的平均长度是k。遍历每个字符串统计频率需要O(k)的时间，生成频率键也需要O(26)也就是O(1)的时间，所以整体时间复杂度是O(n*k)。
- 空间复杂度：哈希表需要存储所有的字符串，空间复杂度是O(n*k)，另外频率数组是固定长度26，属于常数空间，不影响整体复杂度。
和传统排序解法对比，排序解法的时间复杂度是O(n*k log k)，因为排序每个字符串需要O(k log k)的时间，而基于频率的解法不需要排序，在字符串长度较长时，性能会更优。
适用场景说明
这种无排序的实现方式适合对字符串顺序敏感、或者不允许修改原字符串排序的场景。如果字符串中包含的不仅是小写字母，比如有大写字母、数字或者其他字符，只需要调整频率数组的长度，对应不同字符的ASCII码范围即可，核心思路不需要改变。