字母异位词分组 - Stellar Observer Protocol

529 字

3 分钟

字母异位词分组

2025-08-13

Algorithms

数组

/

哈希表

/

字符串

/

排序

题目描述#

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

解题思路#

哈希映射策略：
- 创建哈希表存储分组，键为标准化后的字符串，值为异位词列表
- 标准化方法：
  - 排序法：字符串排序后作为键（"eat" → "aet"）
  - 计数法：字母计数数组转换为字符串（[1,0,0,...,1]）
分组过程：
- 遍历每个字符串，计算其标准化键
- 将原始字符串加入对应键的分组列表
结果提取：
- 返回哈希表中所有值（分组列表）

关键洞察#

标准化核心：
- 字母异位词排序后相同 → 完美分组键
- 计数法避免排序开销（固定长度数组）
分隔符必要性：
- 计数数组需用分隔符连接（防歧义）
- 如 [11,0] 和 [1,10] 不加分隔符相同
哈希表高效性：
- O(1) 时间完成分组插入
- 自动处理新键创建
空间换时间：
- 存储标准化键和分组列表
- 换取近乎线性的时间复杂度

复杂度分析#

方法	时间复杂度	空间复杂度	适用场景
排序法	O(n × k log k)	O(n × k)	字符串短时高效
计数法	O(n × k)	O(n × k + Σ)	字符集固定时更优

注：

n：字符串数量
k：字符串平均长度
Σ：字符集大小（26字母时为26）

代码实现#

排序法

1
/**
2
 * @param {string[]} strs
3
 * @return {string[][]}
4
 */
5
var groupAnagrams = function(strs) {
6
    // 哈希表
7
    const hash = {};
8
    for(let i=0,len=strs.length;i<len;i++){
9
        const str = strs[i];
10
        const key = str.split("").sort().join("-");
11
        if(key in hash) {
12
            hash[key].push(str)
13
        }else{
14
            hash[key] = [str]
15
        }
16
    }
17
    return Object.values(hash);
18
};

计数法

1
const groupAnagrams = (strs) => {
2
    const map = new Map();
3
    const base = 'a'.charCodeAt(0);
4

5
    for (const str of strs) {
6
        const count = Array(26).fill(0);
7
        // 字符计数
8
        for (const char of str) {
9
            count[char.charCodeAt(0) - base]++;
10
        }
11
        // 添加分隔符生成键：'1,0,2,...'
12
        const key = count.join(',');
13
        if (!map.has(key)) map.set(key, []);
14
        map.get(key).push(str);
15
    }
16
    return Array.from(map.values());
17
};