【Hot100-Java中等】：字母异位词分组

在 LeetCode 的字符串题目中，“字母异位词” (Anagrams) 是一个非常高频的概念。这道第 49 题不仅考察了哈希表（HashMap）的应用，更是一个理解 Java 对象机制的绝佳案例。

1. 解决方案一：排序数组分类 (Sorting)

这是最符合直觉的解法。既然“异位词”的字母成分一样，那只要把它们按照字母顺序重新排列，长得就一模一样了。

核心逻辑

1. 遍历每个字符串。

2. 将其转化为字符数组并排序（如"tea"->"aet"）。

3. 以排序后的字符串作为 Key，原始字符串作为 Value 加入 Map。

代码实现

Java

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { char[] array = str.toCharArray(); Arrays.sort(array); // 关键步骤：排序 String key = new String(array); // 关键步骤：使用内容构造 Key List<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<>(map.values()); } }

复杂度分析

• 时间复杂度：。

  • 是字符串的数量。

  • 是字符串的最大长度。

  • 排序每个字符串需要 $O(K \log K)$ 的时间。

• 空间复杂度：。我们需要存储所有字符串的内容。

2. 解决方案二：计数法 (Counting)

如果字符串特别长（很大），排序的可能会成为瓶颈。我们可以利用题目条件：“仅包含小写字母”。

核心逻辑

不排序，而是给字符串做“成分体检”。

1. 用一个长度为 26 的数组int[26]统计每个字母出现的次数。

2. 将这个统计结果转换成一个唯一的 Key。

   • 例如"eat"的统计结果是：a=1, e=1, t=1，其他为0。

   • 我们可以构造一个 Key 字符串，如"a1e1t1..."或者简单的利用 StringBuilder 拼接非零字符和次数。

3. 放入 HashMap。

代码实现

Java

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { // 1. 统计频次 int[] counts = new int[26]; int length = str.length(); for (int i = 0; i < length; i++) { counts[str.charAt(i) - 'a']++; } // 2. 构造唯一 Key // 技巧：将字母和次数拼起来，例如 "a1e1t1" StringBuilder sb = new StringBuilder(); for (int i = 0; i < 26; i++) { if (counts[i] != 0) { sb.append((char) ('a' + i)); sb.append(counts[i]); } } String key = sb.toString(); // 3. 存入 Map List<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<>(map.values()); } }

复杂度分析

• 时间复杂度：。

  • 我们在的时间内统计频次。

  • 在（即 26）的时间内生成 Key。

  • 因为没有了排序，当很大时，这种方法比排序法更快。

• 空间复杂度：。

3. 深度思考：为什么两种方法一种采用new String()初始化，另一种采用toString()？

1. 数组 (char[]) 的toString()：它是“懒惰”的

在 Java 中，数组（无论是int[],char[]还是String[]）虽然是对象，但它们没有重写（Override）Object类的默认toString()方法。

默认行为（Object.toString）是：

返回类名 + @ + 内存地址哈希值

这就是为什么你之前会得到[C@15db9742这种乱码。它告诉你“我是一个字符数组，我住在内存的这个地址”，但它不会告诉你数组里存了什么内容。

• 比喻：你指着一个装满苹果的箱子问：“你是什么？”箱子回答：“我是编号 888 的箱子。”（它不告诉你里面有苹果）。

2.StringBuffer/StringBuilder的toString()：它是“勤奋”的

在方法二中，代码是这样的：

Java

StringBuffer sb = new StringBuffer(); // ... 循环 append 字符和数字 ... String key = sb.toString(); // 这里调用的是 StringBuffer 的 toString

StringBuffer（以及StringBuilder）是专门用来处理字符串的类。它们的源代码里重写了toString()方法。

它们的行为是：

把缓冲区里存储的所有字符，拼接成一个真正的String对象并返回。

• 比喻：你指着一张写满字的纸问：“你是什么？”纸回答：“我上面写着‘a1b2c3’。”（它直接告诉你内容）。

3. 直观对比

我们可以写一段测试代码来看看区别：

Java

char[] arr = {'a', 'b', 'c'}; StringBuffer sb = new StringBuffer(); sb.append('a').append('b').append('c'); // 情况 1：数组调用 System.out.println(arr.toString()); // 输出：[C@6bc7c054 (乱码/地址) -> ❌ 即使内容一样，不同数组地址不同，导致 HashMap 认为是不同 Key // 情况 2：StringBuffer 调用 System.out.println(sb.toString()); // 输出：abc (内容) -> ✅ 只要内容一样，生成的 String 就一样，HashMap 认为是同一个 Key

4. 方法二的巧妙之处

方法二（计数法）之所以能成功，是因为它手动把数组里的统计信息，转化成了一个唯一的字符串。

• 对于 "eat"：

  1. 统计数组：a=1, e=1, t=1

  2. sb.append拼接过程："a1","e1","t1"

  3. sb.toString()结果："a1e1t1"

• 对于 "tea"：

  1. 统计数组：a=1, e=1, t=1

  2. sb.append拼接过程："a1","e1","t1"（顺序是按 a-z 遍历的，所以拼接顺序固定）

  3. sb.toString()结果："a1e1t1"

因为最后生成的都是字符串对象"a1e1t1"，而 Java 的String类比较的是内容（Value），所以 HashMap 判定它们相等。

总结

所以，方法一要想修复，必须显式地把char[]转为String（使用new String(arr)），而不能依赖数组自带的toString()。