0049.字母异位词分组

难度：🟡 中等

标签：哈希表、字符串、排序

链接：49. 字母异位词分组

题目描述

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

字母异位词 是由相同字母用不同顺序排列形成的单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

解题思路

核心思想

本题的核心是识别并聚合所有互为“字母异位词”的字符串。字母异位词的一个关键特性是，它们包含完全相同的字符，且每种字符的数量也完全相同。这意味着，如果我们将一个字母异位词的字符进行排序，它们都会得到完全相同的“签名”字符串。

思路选择

排序 + 哈希表 是解决此问题的标准最优思路。

• 我们可以遍历输入的字符串数组。

• 对于每一个字符串，我们都将其字符进行排序，生成一个唯一的“键”（或“签名”）。

• 我们使用一个哈希表（Map），其 key 是这个排序后的签名字符串，其 value 是一个数组，用于存储所有拥有相同签名的原始字符串。

• 遍历完成后，哈希表中的所有 value 集合，就是我们最终需要的分组结果。

关键步骤

1. 初始化：创建一个哈希表 map。

2. 循环遍历：遍历输入的数组 strs 中的每一个字符串 str。

3. 生成键：将 str 转换为字符数组，对其进行排序，然后再连接成一个新的字符串 key。

4. 分组： a. 检查 map 中是否存在键 key。 b. 如果不存在，则在 map 中创建一个新条目，key 为键，[str] 为值。 c. 如果存在，则将 str 推入 map 中 key 对应的数组中。

5. 返回结果：遍历结束后，map 的所有值（Object.values(map) 或 Array.from(map.values())）就是最终的分组结果。

代码实现

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

    for (const str of strs) {
        // 1. 生成签名键
        const key = str.split('').sort().join('');

        // 2. 检查 map 中是否存在该键
        if (map.has(key)) {
            // 存在，则将当前字符串推入
            map.get(key).push(str);
        } else {
            // 不存在，则创建新条目
            map.set(key, [str]);
        }
    }

    // 3. 返回 map 中所有的值
    return Array.from(map.values());
};

复杂度分析

• 时间复杂度：O(n * k log k) 其中 n 是 strs 数组的长度，k 是数组中字符串的最大长度。我们需要遍历 n 个字符串，对于每个字符串，排序的时间复杂度是 O(k log k)。

• 空间复杂度：O(n * k) 在最坏的情况下（所有字符串都不同），哈希表需要存储所有字符串的信息。

相关题目

• 0242.有效的字母异位词

• 0349.两个数组的交集

• 0017.电话号码的字母组合

总结

本题是哈希表应用的经典案例。通过将一个复杂的问题（判断字母异位）转化为一个简单的、可作为键的“范式”（Canonical Form），即排序后的字符串，可以极大地简化分组和聚合的逻辑。这种“创建签名/键”的思路在很多问题中都有应用。