手帐 Blog

主题

复盘 · LC 49 字母异位词分组 ​

题目 ​

题意 ​

给字符串数组 strs，把互为字母异位词的字符串分到同一组（字母相同、顺序可不同）。

  • 返回任意顺序的分组列表。
  • 约束：字符串通常只含小写字母；长度与数组规模要考虑 key 的构造成本。

边界：空串、单字母、完全相同的串、没有异位关系的串各成一组。

涉及算法 ​

标签一句话
哈希表分组同一「特征 key」进同一桶
排序作 keysort 后字符串作签名
计数作 key26 维频次串 / 元组作签名，避免逐词排序

教程对照：09 · 哈希表进阶（异位词分组是该篇核心例题）。

评价我的解法 ​

两版：先手搓数值指纹（错），再改成排序 key（对）。

第一版（错误尝试） ​

意图接近「用质数/幂次编码频次」，但落地成易碰撞的整数 key。

我的代码（摘自 49-字母异位词分组/index2.js，省略测例与 two 辅助里的无关注释）：

javascript
var groupAnagrams = function (strs) {
  const charMap = {
    a: 1, b: 2, c: 3, d: 4, e: 5, f: 6, g: 7, h: 8, i: 9, j: 10,
    k: 11, l: 12, m: 13, n: 14, o: 15, p: 16, q: 17, r: 18, s: 19,
    t: 20, u: 21, v: 22, w: 23, x: 24, y: 25, z: 26,
  };
  const newCharMap = {};
  const twoArr = two(26);
  let i = 0;
  for (const item in charMap) {
    newCharMap[item] = twoArr[i];
    i++;
  }
  const resMap = new Map();
  for (let i = 0; i < strs.length; i++) {
    const str = strs[i];
    let key = 0;
    let keyCharArr = [];
    for (let j = 0; j < str.length; j++) {
      const ch = str.slice(j, j + 1);
      let count = 0;
      keyCharArr.forEach((item) => {
        if (item === ch) count++;
      });
      key += newCharMap[ch] * (count * 114514 + 1);
      keyCharArr.push(ch);
    }
    const curValue = resMap.get(key);
    if (!curValue) {
      resMap.set(key, [str]);
    } else {
      curValue.push(str);
    }
  }
  const res = [];
  resMap.forEach((val) => {
    res.push(val);
  });
  return res;
};

function two(target) {
  const res = [];
  for (let i = 0; i < target; i++) {
    res.push(2 ** i);
  }
  return res;
}

错在哪：

  1. 整数指纹会撞：2^i * (次数权重) 在长串/多重复字符时不保证唯一，异位词分组的 key 必须可证明等价。
  2. 逻辑过重：手写 charMap、再映射成幂次、再用 keyCharArr 数第几次出现——本质想做「计数」，却绕开了 26 维计数数组。
  3. 原文件里还有调试 console.log；curKeyValue 未使用。

方向可以理解成「想编码频次」；正确落地应是 26 计数拼字符串，而不是自定义大整数。

第二版（终解） ​

我的代码（摘自 49-字母异位词分组/index.js）：

javascript
var groupAnagrams = function (strs) {
  const map = new Map();
  for (const str of strs) {
    const key = str.split("").sort().join();
    if (!map.has(key)) {
      map.set(key, [str]);
    } else {
      map.get(key).push(str);
    }
  }
  return Array.from(map.values());
};

对在哪：

  1. 分组骨架正确：key → 数组，最后 Array.from(map.values())。
  2. 异位词签名：排序后字符序列相同 ⟹ 同一 key；join() 默认逗号分隔，对字符数组足够唯一。
  3. 实现短、可读，面试口述成本低。

可改进：每个串排序 O(k log k)，总 O(n · k log k)；计数签名可压到 O(n · k)，但排序版完全可过本题。

小结：终解合格，对齐教程 09。index2 说明你在找更聪明的编码——想法靠近计数，工具选错了。

最佳题解 ​

排序 key（与今日终解同族，略整理）：

javascript
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map();
  for (const str of strs) {
    const key = str.split("").sort().join("");
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(str);
  }
  return Array.from(map.values());
};

计数 key（略优常数/复杂度，面试可提）：

javascript
var groupAnagrams = function (strs) {
  const map = new Map();
  for (const str of strs) {
    const cnt = new Array(26).fill(0);
    for (const ch of str) cnt[ch.charCodeAt(0) - 97]++;
    const key = cnt.join("#");
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(str);
  }
  return Array.from(map.values());
};
  • 排序版：时间 O(n · k log k)，空间 O(n · k)。
  • 计数版：时间 O(n · k)，空间 O(n · k)。
  • 为何计数更优：签名线性扫一遍字符即可，不必对每个串排序。

关联题目 ​

题为何相关
242. 有效的字母异位词分组的「二元版」：只判是否同一签名
438. 找到字符串中所有字母异位词异位 + 滑动窗口
347. 前 K 个高频元素同属哈希计数 / 分组后取结果

一句话带走 ​

异位词分组：Map 按签名分桶；签名优先「排序串」或「26 计数串」，别手搓易碰撞的数字哈希。