49. 字母异位词分组

题目

力扣题目

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

字母异位词由相同字母以不同排列组成，每个字母的出现次数也相同。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

考察内容

• 为一组等价对象设计统一键
• 字符串排序
• 哈希表分组
• 空字符串与重复字符串的处理
• 时间复杂度分析

解题思路

排序后的字符串作为键

字母异位词虽然字符顺序不同，但将字符按字典序排序后会得到完全相同的字符串。例如：

"eat" → "aet"
"tea" → "aet"
"ate" → "aet"

因此可以使用哈希表：

• 键：当前字符串排序后的结果；
• 值：所有具有该排序结果的原字符串。

遍历输入数组时，为每个字符串复制一个 key 并排序，然后执行 groups[key].push_back(str)。遍历结束后，将哈希表中的每个分组放入结果数组。

样例的分组过程如下：

设字符串数量为 n，每个字符串的最大长度为 k：

• 排序所有字符串的时间复杂度：$O(nk\log k)$
• 哈希和收集结果的期望时间复杂度：$O(nk)$
• 空间复杂度：$O(nk)$，用于哈希键和结果分组

字母计数作为键

因为题目限定只有 26 个小写字母，也可以统计每个字母的出现次数，将 26 维计数编码成键。这样单个字符串的处理可从 $O(k\log k)$ 降到 $O(k)$，但键的编码方式更复杂。

代码演示

std::vector<std::vector<std::string>> groupAnagrams(
    const std::vector<std::string>& strs) {
    std::unordered_map<std::string, std::vector<std::string>> groups;

    for (const std::string& str : strs) {
        std::string key = str;
        std::sort(key.begin(), key.end());
        groups[key].push_back(str);
    }

    std::vector<std::vector<std::string>> result;
    result.reserve(groups.size());

    for (auto& [key, group] : groups) {
        result.push_back(std::move(group));
    }

    return result;
}

易错点

• 直接使用原字符串作为键：异位词的字符顺序不同，无法被分到同一组。
• 排序原字符串本身：结果中需要保留原始字符串，应复制到 key 后再排序。
• 只比较字符种类，忽略出现次数："abb" 和 "ab" 不是异位词。
• 认为结果顺序固定：题目允许分组顺序和组内顺序任意，哈希表遍历顺序本身也不稳定。
• 遗漏空字符串：空字符串排序后仍为空字符串，可以自然作为哈希键。
• 计数键连接时产生歧义：若使用计数法，不能直接无分隔拼接数字；例如计数 1,11 与 11,1 必须能够区分。

总结

本题的核心不是排序本身，而是为所有字母异位词构造同一个“规范表示”。排序后的字符串天然满足这一点，再使用哈希表按照规范键分组即可。

相关题目

• 242. 有效的字母异位词
• 249. 移位字符串分组
• 438. 找到字符串中所有字母异位词
• 451. 根据字符出现频率排序