本文详细探讨了一种在leetcode中无需排序即可对字符串数组进行变位词分组的java解决方案。该方法巧妙地利用字符频率数组作为hashmap的键，将具有相同字符组成（即变位词）的字符串高效地归类。文章深入解析了`arrays.tostring()`在此过程中的关键作用，并提供了详细的代码实现及严谨的时间复杂度`o(m*n)`分析，其中`m`为字符串数量，`n`为平均字符串长度。
变位词分组的核心思想
变位词（Anagrams）是指由相同字母以不同顺序排列而成的单词或短语，例如 "eat", "tea", "ate" 都是彼此的变位词。传统的变位词判断方法通常涉及对字符串进行排序，然后比较排序后的结果。然而，这种方法对于每个字符串都需要O(N log N)的时间复杂度。为了优化性能，我们可以采用一种无需排序的方法：字符频率计数。
其核心思想是：如果两个字符串是变位词，那么它们包含的每个字符的数量必然是相同的。例如，"eat" 和 "tea" 都包含一个 'e'，一个 'a'，一个 't'。因此，我们可以为每个字符串构建一个字符频率“指纹”，并使用这个指纹作为哈希表的键来将变位词分组。
基于字符频率数组的实现
在Java中，我们可以使用一个长度为26的整型数组来记录每个小写英文字母的出现次数。数组的每个索引对应一个字母（0对应'a'，1对应'b'，以此类推）。
-
构建频率数组：对于输入数组中的每个字符串str，初始化一个int[26]的数组input。遍历str中的每个字符c，通过input[c - 'a']++来增加对应字符的计数。 例如，对于字符串 "eat"：
- input['e' - 'a'] 增加 1
- input['a' - 'a'] 增加 1
- input['t' - 'a'] 增加 1 最终，input 数组可能看起来像 [1, 0, 0, 0, 1, 0, ..., 1, ..., 0]，其中 'a', 'e', 't' 对应的位置是 1，其余为 0。
-
生成哈希键：关键在于如何将这个int[26]数组转换为一个可以作为HashMap键的唯一标识。Arrays.toString(input) 方法在此发挥了巧妙的作用。它会将整型数组转换成一个字符串表示，例如 "[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]"。 这个字符串是唯一且一致的，因为：
- 任何变位词（如 "eat", "tea", "ate"）都会生成完全相同的字符频率数组。
- Arrays.toString() 会将相同的数组内容转换成相同的字符串。 因此，这个字符串就成为了变位词组的理想哈希键。
-
分组存储：使用一个HashMap
>来存储分组结果。键是上述生成的频率数组字符串，值是一个List ，包含所有具有该频率模式的原始字符串。 立即学习“Java免费学习笔记（深入）”；
- 如果outputMap中已存在该频率字符串作为键，则将当前字符串添加到对应的List中。
- 如果不存在，则创建一个新的List，将当前字符串添加进去，并将该频率字符串作为键，新List作为值存入outputMap。
收集结果：遍历完所有输入字符串后，outputMap中的所有值（即List
）就是最终的分组结果。将其收集到一个List - >中返回。
示例代码
以下是该方法的Java实现：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AnagramGrouper {
public List> groupAnagrams(String[] strs) {
List> output = new ArrayList<>();
if (strs == null || strs.length == 0) {
return output;
}
Map> outputMap = new HashMap<>();
for (String str : strs) {
// 1. 构建字符频率数组
int[] charCounts = new int[26]; // 26个小写英文字母
for (char c : str.toCharArray()) {
charCounts[c - 'a']++;
}
// 2. 将频率数组转换为字符串作为HashMap的键
String frequencyKey = Arrays.toString(charCounts);
// 3. 根据键进行分组存储
if (outputMap.containsKey(frequencyKey)) {
outputMap.get(frequencyKey).add(str);
} else {
List anagramList = new ArrayList<>();
anagramList.add(str);
outputMap.put(frequencyKey, anagramList);
}
}
// 4. 收集所有分组结果
output.addAll(outputMap.values());
return output;
}
public static void main(String[] args) {
AnagramGrouper grouper = new AnagramGrouper();
String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
List> result1 = grouper.groupAnagrams(strs1);
System.out.println("示例1分组结果: " + result1);
// 预期输出可能为: [[bat], [nat, tan], [eat, tea, ate]] (顺序可能不同)
String[] strs2 = {""};
List> result2 = grouper.groupAnagrams(strs2);
System.out.println("示例2分组结果: " + result2); // 预期输出: [[]]
String[] strs3 = {"a"};
List> result3 = grouper.groupAnagrams(strs3);
System.out.println("示例3分组结果: " + result3); // 预期输出: [[a]]
}
} 时间复杂度分析
该算法的时间复杂度可以按以下步骤进行分析：
外层循环：遍历输入字符串数组strs，假设数组中有m个字符串。这一步的复杂度是O(m)。
内层循环（字符计数）：对于每个字符串str，我们都需要遍历其所有字符来构建频率数组。假设字符串的平均长度为n。那么，对于每个字符串，此操作的复杂度是O(n)。
Arrays.toString()：将长度为26的int数组转换为字符串。由于数组长度是固定的常数26，此操作的复杂度是O(1)（或者更精确地说，O(26)，可以简化为O(1)）。
HashMap操作：containsKey(), get(), put(), add()等操作在平均情况下都具有O(1)的时间复杂度。在最坏情况下（哈希冲突严重），可能退化到O(k)，其中k是键的长度。在这里，我们的键是一个字符串，其长度也是固定的常数（Arrays.toString()生成的字符串长度固定，与26个字符的数组相关）。因此，这些操作可以视为O(1)。
综合以上分析，总时间复杂度为：
- 外层循环执行m次。
- 每次外层循环中，执行O(n)的字符计数操作。
- 每次外层循环中，执行O(1)的Arrays.toString()操作。
- 每次外层循环中，执行O(1)的HashMap和ArrayList操作。
因此，总时间复杂度可以表示为 m * (n + 1 + 1)，即 O(m * n + 2m)。当m和n足够大时，常数项和较低次项可以忽略，最终的时间复杂度为 *`O(m n)`**。
注意事项与总结
-
字符集限制：此方案假设输入字符串只包含小写英文字母。如果包含大写字母、数字或其他字符，需要调整频率数组的大小（例如，使用128或256来覆盖ASCII码）或使用HashMap
来存储频率。 -
空间复杂度：空间复杂度主要取决于HashMap存储的键值对数量。最坏情况下，所有字符串都不是变位词，HashMap会存储m个键，每个键是一个字符串（长度固定），每个值是一个List
。因此，空间复杂度为O(m * k)，其中k是键的长度，可以简化为O(m)。此外，每个List 会存储原始字符串，因此还需要O(总字符数)的空间。 - 性能优势：相较于对每个字符串进行排序的方法，这种基于频率计数的方法避免了对字符串内部进行比较排序的O(N log N)开销，在许多情况下能够提供更好的性能。
通过巧妙地利用字符频率数组和Arrays.toString()方法，我们能够高效地解决变位词分组问题，为处理大量字符串数据提供了一个优化方案。
