0049. Group Anagrams¶
题目信息¶
- 题号:
字母异位词分组
- 难度:
Medium
- 主题:
字符串、哈希表、规范键、字符频次
- 原题:
- 重点:
从反复比较是否为异位词,推导到为每个字符串计算唯一组签名并一次归组
题目重述¶
给定一个字符串数组 strs,其中每个字符串只包含小写英文字母。请把互为字母异位词的字符串放入同一组,
并返回所有分组。
两个字符串互为字母异位词,当且仅当它们包含完全相同的字母,并且每种字母的出现次数也完全相同。 字符串内部字母的排列顺序不影响所属分组。每个输入字符串都必须保留一次;若相同字符串在输入中出现多次, 结果中也必须保留相同次数。分组之间以及同一组内部的顺序均不限。
约束为 1 <= strs.length <= 10^4、0 <= strs[i].length <= 100。
自建示例¶
输入:strs = ["arc", "car", "rat", "tar", "elbow", "below", "arc", ""]
输出:[["arc", "car", "arc"], ["rat", "tar"], ["elbow", "below"], [""]]
"arc" 与 "car" 的三个字母及次数相同,因此属于同一组;输入中的第二个 "arc" 仍须保留。
空字符串的 26 种字母次数全为零,也有唯一签名。
C++ 实现¶
#include <algorithm>
#include <array>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
class Solution {
private:
bool haveSameFrequency(const std::string& first, const std::string& second) {
if (first.size() != second.size()) return false;
std::array<int, 26> count{};
for (char ch : first) ++count[ch - 'a'];
for (char ch : second) {
if (--count[ch - 'a'] < 0) return false;
}
return true;
}
std::vector<std::vector<std::string>> pairwiseGrouping(
const std::vector<std::string>& words
) {
std::vector<std::vector<std::string>> groups;
for (const std::string& word : words) {
bool placed = false;
for (auto& group : groups) {
if (!haveSameFrequency(word, group.front())) continue;
group.push_back(word);
placed = true;
break;
}
if (!placed) groups.push_back({word});
}
return groups;
}
std::vector<std::vector<std::string>> sortedSignatureGrouping(
const std::vector<std::string>& words
) {
std::unordered_map<std::string, int> groupIndex;
std::vector<std::vector<std::string>> groups;
for (const std::string& word : words) {
std::string signature = word;
std::sort(signature.begin(), signature.end());
auto [it, inserted] = groupIndex.emplace(
signature,
static_cast<int>(groups.size())
);
if (inserted) groups.push_back({});
groups[it->second].push_back(word);
}
return groups;
}
std::string buildFrequencySignature(const std::string& word) {
std::array<int, 26> count{};
for (char ch : word) ++count[ch - 'a'];
std::string signature;
for (int frequency : count) {
signature.push_back('#');
signature += std::to_string(frequency);
}
return signature;
}
std::vector<std::vector<std::string>> frequencySignatureGrouping(
const std::vector<std::string>& words
) {
std::unordered_map<std::string, int> groupIndex;
std::vector<std::vector<std::string>> groups;
for (const std::string& word : words) {
std::string signature = buildFrequencySignature(word);
auto [it, inserted] = groupIndex.emplace(
std::move(signature),
static_cast<int>(groups.size())
);
if (inserted) groups.push_back({});
groups[it->second].push_back(word);
}
return groups;
}
public:
std::vector<std::vector<std::string>> groupAnagrams(
std::vector<std::string>& strs
) {
return frequencySignatureGrouping(strs);
}
};
题解¶
逐组比较基线¶
最直接的做法是维护已经建立的分组。处理新字符串时,把它依次与每组的代表字符串比较;字符频次相同就加入该组, 所有组都不匹配时再新建一组。
代表字符串足以判断组别。异位词关系只取决于 26 种字符的出现次数,同一组中的字符串都与代表具有相同频次, 因此彼此也具有相同频次。
pairwiseGrouping 正确地保留了每个输入元素,但会反复计算频次。若已经形成 g 个组,新字符串最坏需要执行
g 次比较;当大部分字符串互不相同时,组数接近字符串数量,整体退化为平方级。
从比较到签名¶
逐组比较反复询问“当前字符串与这个代表是否同组”。可以改为给每个字符串计算一次规范签名,并要求:
两个字符串互为异位词 <=> 两个签名完全相同
签名相同的字符串直接进入同一哈希桶,不再逐个尝试已有代表。算法的核心因此从两两判定变成构造能够完整表示字符 多重集合的键。
排序签名¶
把字符串中的字符排序,排列顺序被消除。例如:
arc -> acr
car -> acr
rat -> art
异位词拥有相同字符及次数,排序结果必然相同;排序结果相同也说明每个字符及其次数完全一致。因此排序后的字符串是 异位词类别的充要签名。
sortedSignatureGrouping 对每个字符串生成排序副本,再通过哈希表找到对应组。该方法简单,并且适用于字符集合不固定
的情况;长度为 k 的字符串需要 O(k log k) 时间生成签名。
频次签名¶
本题字符集合固定为 26 个小写字母,可以直接使用频次数组:
count[0] 记录 a 的数量
count[1] 记录 b 的数量
...
count[25] 记录 z 的数量
两个字符串互为异位词,当且仅当 26 个分量逐项相等。生成频次只需扫描字符串,不再需要排序。
代码把频次数组序列化为字符串键。每个分量前加入 # 分隔符:
[1, 11, 0, ...] -> #1#11#0...
[11, 1, 0, ...] -> #11#1#0...
分隔符保留了每个计数的边界;若直接连接十进制数字,[1, 11] 与 [11, 1] 都可能变成 111,从而把
不同频次向量错误地放入同一组。
签名分桶不变量¶
groupIndex[signature] 保存该签名对应的结果组下标。处理每个字符串时保持以下状态:
groups已经包含所有处理过的字符串,并且每个字符串恰好出现一次;groupIndex中每个签名只对应一个组;同一组中的字符串具有相同签名,不同组的签名不同。
首次看到某个签名时,在 groups 末尾建立新组,并登记它的下标;以后相同签名直接追加到原组。由于签名与字符
频次一一对应,同组字符串必然互为异位词,不同组至少有一个频次分量不同。
外层循环对每个输入字符串执行一次追加,因此不会遗漏或额外复制。相同字符串在输入中重复出现时,每次都会再次追加, 原有重复次数也被完整保留。空字符串的 26 项计数全为零,同样拥有唯一签名。
状态演化¶
处理 ["eat", "tea", "tan", "ate", ""] 时:
字符串 |
签名关系 |
操作 |
|---|---|---|
|
首次出现 |
建立组 0,加入 |
|
与 |
加入组 0 |
|
首次出现 |
建立组 1,加入 |
|
与 |
加入组 0 |
空字符串 |
26 项全为 0 |
建立组 2 |
哈希表只保存组下标,结果数组可以在读取输入时直接构造,也不依赖哈希表最终的遍历顺序。
代码演进¶
pairwiseGrouping 逐组寻找代表,逻辑直接,但相同频次被重复计算。
sortedSignatureGrouping 为每个字符串建立排序规范键,把逐组搜索改为一次哈希查询。
frequencySignatureGrouping 利用固定字符集合,以线性扫描生成频次签名。公开入口采用该方法,因为它避免了每个字符串
内部的排序。
复杂度分析¶
设字符串数量为 n,总字符数为 C,最长字符串长度为 k。
逐组比较在组数接近 n 时需要 O(n^2 k) 时间。排序签名方法需要
O(sum(len(word) log len(word))) 时间,可粗略写成 O(nk log k)。
频次签名扫描全部字符需要 O(C),每个字符串还要序列化固定的 26 个计数,因此总时间为 O(C + n)。
不计返回结果中的字符串存储,哈希键和组索引使用 O(n) 额外空间;26 维计数属于常量空间。