跳到主要内容

LeetCode 49. 字母异位词分组

本节目标

用字符频次数组构造稳定键，把字母组成相同的字符串归入同一组。

这道题承接哈希表解题框架：不再把一个值映射到一个下标，而是把同一种字符串特征映射到一个字符串列表。

查看原题

题意与约束​

给定一个字符串数组，把由相同字母组成、仅排列顺序不同的字符串分成同一组。组与组、组内字符串的返回顺序都不影响答案；所有字符串只含小写英文字母。

关键是为每个字符串找到同一个“代表”。只要两个字符串的代表相同，它们就应落入同一个映射值列表。

先用排序理解规范化键​

朴素但正确的代表是把字符串字符排序。例如 "tea" 与 "eat" 排序后都是 "aet"，所以排序后的字符串可以作为键。它说明了规范化的含义：不同外观的输入经同一转换后，等价对象得到完全相同的结果。

不过排序会随字符串长度增长。题目中的字符种类固定为 26 个小写字母，可以继续问：我们真正关心的是排序后的顺序，还是每个字母出现了几次？后者已经足以唯一确定一组异位词。

用频次数组构造键​

遍历每个字符串，建立长度为 26 的频次数组，位置 0 到 25 分别记录 a 到 z 的出现次数。相同的字母多重集合必然得到相同数组，不同多重集合也至少有一个计数不同。

C++ 把 26 个计数用分隔符拼成字符串键，避免如 1, 11 与 11, 1 在无分隔符时产生歧义；Python 直接把列表转成不可变的 26 元组。映射的值是字符串列表，每遇到一个键就把原字符串追加进去。

代码实现​

两份源码都只统计字符频次，不为输出顺序额外排序。评测允许任意分组顺序，测试会在比较前规范化结果。

C++17
#include <array>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (const string& str : strs) {
            array<int, 26> count{};
            for (char ch : str) {
                count[ch - 'a']++;
            }

            string key;
            for (int frequency : count) {
                key += to_string(frequency) + '#';
            }
            groups[key].push_back(str);
        }

        vector<vector<string>> result;
        result.reserve(groups.size());
        for (auto& [key, group] : groups) {
            result.push_back(group);
        }
        return result;
    }
};

复杂度分析​

设所有字符串的总字符数为 S，字符串数量为 n。

  • 时间复杂度：O(S + 26n)，每个字符统计一次，每个字符串再扫描固定的 26 个桶来构造键；通常可写作 O(S)。
  • 空间复杂度：O(S + 26n)，分组结果保存所有字符串，映射键为每个不同分组保存固定长度特征；除结果外的临时频次数组是 O(26)。

排序键的单串代价是 O(L log L)，频次数组把这部分改为 O(L + 26)，并直接利用了字符集固定的约束。

易错点​

  • 只用字符串长度作键：长度相同不表示字母组成相同。
  • 把可变列表直接当作 Python 字典键：列表不可哈希，应转换为元组。
  • C++ 拼接计数时省略分隔符：不同计数组合可能得到同一文本。
  • 为了固定输出而修改算法：题意不要求顺序，分组逻辑只需保证同类进入同一列表。

模式迁移​

当题目要求“按某种等价关系分组”时，先寻找能把等价对象变成同一键的规范化过程。字符串可排序或统计频次；数组可排序、取差值或提取签名；图形和状态也常能提取不可变特征。下一题最长连续序列不再需要恢复分组成员，只需判断值是否存在，因此映射可以进一步简化为集合。