49. 字母异位词分组

LeetCode 原题链接

题目描述

给定一个字符串数组 strs，将其中的字母异位词组合在一起，并以二维数组的形式返回。答案可以按任意顺序返回。

字母异位词是由相同字母重新排列形成的字符串，每个字母的出现次数也必须相同。

示例：

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
输入：strs = [""]
输出：[[""]]
输入：strs = ["a"]
输出：[["a"]]

1. 题型判断

本题的重点不是比较任意两个字符串，而是为每组字母异位词找到一个相同且唯一的标识。

这个标识通常称为规范化键：

  • 字母异位词生成相同的键。
  • 非字母异位词生成不同的键。

得到键后，用哈希表维护下面的映射：

规范化键 -> 具有该键的所有原字符串

常见的键有两种：

  1. 将字符串中的字符排序，排序结果作为键。
  2. 统计 26 个小写字母的出现次数，频次数组作为键。

2. 解法一：排序作为键

两个字符串互为字母异位词，当且仅当它们排序后的结果相同。

例如：

"eat" -> "aet"
"tea" -> "aet"
"ate" -> "aet"

因此可以遍历每个字符串：

  1. 将字符串拆分为字符数组并排序。
  2. 将排序结果拼接为字符串，作为哈希表的键。
  3. 把原字符串加入该键对应的分组。
  4. 最后返回哈希表中的所有分组。

示例推演

对于 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]：

原字符串排序后的键哈希表中该键对应的分组
eataet[eat]
teaaet[eat, tea]
tanant[tan]
ateaet[eat, tea, ate]
natant[tan, nat]
batabt[bat]

最终取出哈希表的所有值即可。题目允许分组以及组内字符串按任意顺序返回。

JavaScript 实现

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const groups = new Map();

  for (const str of strs) {
    const key = str.split("").sort().join("");

    if (!groups.has(key)) {
      groups.set(key, []);
    }

    groups.get(key).push(str);
  }

  return Array.from(groups.values());
};

复杂度分析

设字符串数量为 n，最长字符串的长度为 k：

  • 时间复杂度：O(n × k log k)。每个字符串排序需要 O(k log k)。
  • 空间复杂度：O(n × k)。哈希表保存分组和键；若不计返回结果，排序产生的临时字符数组也需要 O(k) 空间。

3. 解法二：字母频次作为键

题目中的字符串只包含小写英文字母，因此可以用长度为 26 的数组统计每个字母出现的次数。

例如：

"abbc" -> a:1, b:2, c:1，其余字母为 0
"bcab" -> a:1, b:2, c:1，其余字母为 0

两者的频次完全一致，所以属于同一组。

JavaScript 的 Map 对数组键按引用比较。即使两个数组内容相同，只要不是同一个对象，就会被视为不同的键。因此不能直接将 count 数组作为键，而应把它序列化为字符串：

const key = count.join("#");

分隔符可以消除数字直接拼接时的歧义。例如，没有分隔符时，计数 [1, 11] 和 [11, 1] 都可能被错误拼成 "111"。

JavaScript 实现

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const groups = new Map();
  const baseCode = "a".charCodeAt(0);

  for (const str of strs) {
    const count = new Array(26).fill(0);

    for (const char of str) {
      count[char.charCodeAt(0) - baseCode]++;
    }

    const key = count.join("#");

    if (!groups.has(key)) {
      groups.set(key, []);
    }

    groups.get(key).push(str);
  }

  return Array.from(groups.values());
};

复杂度分析

设字符串数量为 n，最长字符串的长度为 k。字符集大小固定为 26：

  • 时间复杂度：O(n × k)。每个字符只统计一次，构造长度为 26 的键是常数开销。
  • 空间复杂度：O(n × k)。主要空间用于保存哈希表中的字符串分组和键；单个频次数组只需要 O(1) 额外空间。

如果字符集并非固定大小，构造频次键的成本还需要计入字符集大小。

4. 两种解法如何选择

方案时间复杂度优点限制
排序键O(n × k log k)直观、代码短、适用于更一般的字符集合每个字符串都需要排序
频次键O(n × k)无需排序，理论复杂度更优依赖有限且已知的字符集，需要正确序列化键

面试中通常先写排序解法，因为它简单可靠；如果面试官追问优化，再说明可以利用“小写英文字母”这一条件改用频次键。

5. 正确性说明

以排序键为例：

  • 如果两个字符串互为字母异位词，那么它们包含的字符及各字符出现次数完全相同，排序后必然得到相同字符串，因此会进入同一组。
  • 如果两个字符串排序后的键相同，那么它们包含的字符及出现次数也完全相同，因此它们一定互为字母异位词。

所以，“属于同一组”和“规范化键相同”互为充要条件，哈希分组不会遗漏或错误合并字符串。

频次键的证明相同：频次数组相等，当且仅当每个字母的出现次数都相等。

6. 边界条件与易错点

边界条件：

  • 空字符串的排序键是 ""，所有空字符串会自然归为一组。
  • 单字符字符串只有与自身字符相同的字符串才能归为一组。
  • 输入中出现重复字符串时，应保留每一次出现，不能去重。
  • 不同长度的字符串不可能是字母异位词，它们生成的规范化键也一定不同。

易错点：

  • 加入分组的是原字符串 str，不是排序后的 key。
  • JavaScript 默认按 Unicode 字符串顺序排序字符，本题只有小写英文字母，可以直接使用 sort()。
  • 不要用普通对象后直接返回 Object.values 而忽略原型键等问题；Map 更适合表达这里的映射关系。
  • 频次法不能直接使用数组作为 Map 的键，因为数组按引用而不是内容比较。
  • 频次数组必须为每个字符串重新创建或清零，否则上一个字符串的计数会污染下一个字符串。

7. 面试追问

为什么不逐对判断两个字符串是否互为异位词？

逐对比较需要检查约 n² 对字符串，即使单次判断只需 O(k)，总时间仍会达到 O(n² × k)。规范化键让每个字符串只处理一次，再借助哈希表直接找到所属分组。

如果字符串包含大写字母或 Unicode 字符怎么办？

排序法通常无需改变核心逻辑。频次法则不能再固定使用长度为 26 的数组，可以使用 Map 统计实际字符，并以稳定顺序序列化频次；还要根据需求明确按 Unicode 码点还是用户感知字符进行处理。

返回结果的顺序稳定吗？

JavaScript 的 Map 按键首次插入的顺序迭代，因此上述实现中的组顺序由每个规范化键第一次出现的位置决定，组内顺序与输入顺序一致。不过题目允许任意顺序，不应让正确性依赖这一特性。

8. 可迁移总结

这道题的核心模式是：

对象 -> 规范化键 -> 哈希分组

当题目要求按“本质相同”对元素分类时，可以依次思考：

  1. 什么条件决定两个元素等价？
  2. 能否为每个等价类构造唯一的规范化表示？
  3. 能否用哈希表把具有相同表示的元素一次性归组？

这个思路也常用于旋转等价、排列等价、约分后的比例分组以及按特征签名聚类等问题。