algorithms►leetcode

006-字母异位词分组

字母异位词分组

  1. 新建Map()
  2. 给词按字母顺序排序；
  3. 将排序后的字符作为键，map根据键向里面放数据；
  4. 最后返回map的值

方法一：排序 + 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function groupAnagrams(strs) {
    const map = new Map();
    
    for (const str of strs) {
        // 将字符串排序后作为键
        const key = [...str].sort().join('');
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(str);
    }
    
    return Array.from(map.values());
}

方法二：计数 + 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function groupAnagrams(strs) {
    const map = new Map();
    
    for (const str of strs) {
        const count = new Array(26).fill(0);
        for (const char of str) {
            count[char.charCodeAt() - 'a'.charCodeAt()]++;
        }
        // 将计数数组转换为字符串作为键
        const key = count.join('#');
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(str);
    }
    
    return Array.from(map.values());
}

使用示例

1
2
3
const strs = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagrams(strs));
// 输出: [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]

方法比较

  1. 排序法：

    • 更直观，代码更简洁
    • 时间复杂度：O(n * k log k)，其中n是字符串数量，k是字符串最大长度

  2. 计数法：

    • 更高效，特别是对于长字符串
    • 时间复杂度：O(n * k)
    • 需要处理字符计数字符串化的方式（这里使用#分隔）

注意事项

  • 在JavaScript中，对象不能直接作为Map的键（会被转为字符串”[object Object]”），所以计数法需要将数组转换为特定格式的字符串
  • 字符计数时使用charCodeAt()方法获取ASCII码
  • Array.from(map.values())将Map的值转换为数组

两种方法都能有效解决问题，根据实际场景选择合适的方法。