字母异位词分组

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：哈希表、字符串处理、排序

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

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

示例 2：
输入：strs = [""]
输出：[[""]]

示例 3：
输入：strs = ["a"]
输出：[["a"]]

2. 解题思路拆解

方法：哈希表 + 排序

两个字符串互为字母异位词，意味着它们包含的字符种类和数量完全相同，只是顺序不同。

因此，如果我们对这两个字符串中的字符进行排序，它们得到的字符串一定是相同的。我们可以利用这个特性作为哈希表的键 (Key)。

初始化一个哈希表 Map，键为排序后的字符串，值为原始字符串组成的数组。
遍历输入数组 strs 中的每个字符串 str：
- 将 str 转换为字符数组，进行排序，再拼接回字符串，得到 key。
- 检查 Map 中是否存在该 key。
- 如果存在，将 str 追加到对应的数组中。
- 如果不存在，新建一个数组 [str] 并存入 Map。
遍历结束后，Map 中所有的值 (values) 构成的集合即为结果。

3. 代码实现

javascript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let map = new Map();
    for (let str of strs) {
        // 将字符串转为数组 -> 排序 -> 转回字符串，作为唯一的 Key
        let key = Array.from(str).sort().join('');
        
        // 如果 Key 对应的数组不存在，则初始化
        if (!map.has(key)) {
            map.set(key, []);
        }
        
        // 将原字符串放入对应的分组
        map.get(key).push(str);
    }
    return Array.from(map.values());
};

代码执行演示

假设输入 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]，代码执行过程如下：

初始化：map 为空 {}。
处理 "eat"：
- 排序后 Key 为 "aet"
- Map 中无 "aet" -> 存入 { "aet" => ["eat"] }
处理 "tea"：
- 排序后 Key 为 "aet"
- Map 中有 "aet" -> 追加 { "aet" => ["eat", "tea"] }
处理 "tan"：
- 排序后 Key 为 "ant"
- Map 中无 "ant" -> 存入 { "aet" => ..., "ant" => ["tan"] }
处理 "ate"：
- 排序后 Key 为 "aet" -> 追加 { "aet" => ["eat", "tea", "ate"] }
处理 "nat"：
- 排序后 Key 为 "ant" -> 追加 { "ant" => ["tan", "nat"] }
处理 "bat"：
- 排序后 Key 为 "abt"
- Map 中无 "abt" -> 存入 { ..., "abt" => ["bat"] }
输出结果：提取 Values -> [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

4. 复杂度分析

维度	描述
时间复杂度	$O(n \times k \log k)$。 - $n$ 是字符串的数量。 - $k$ 是字符串的最大长度。我们需要遍历 $n$ 个字符串，每个字符串进行排序需要 $O(k \log k)$ 的时间。注：如果 $k$ 非常大，可以使用“计数法”将复杂度优化至 $O(n \times k)$。
空间复杂度	$O(n \times k)$。需要用哈希表存储全部字符串。

字母异位词分组 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：哈希表 + 排序 ​

3. 代码实现 ​

代码执行演示 ​