🎯 题目描述
给定一个字符串数组，将所有字母异位词组合在一起。字母异位词指的是由相同字母重排形成的字符串，例如"eat"和"tea"。可以按任意顺序返回结果列表。
💡 核心思路
要解决这个问题，关键是找到一种统一的标识，让所有字母异位词都对应同一个标识，这样就能用哈希表把它们分组。
我这里提供两种主流思路：
1. 排序法（直观易实现）
- 核心逻辑：将每个字符串排序，排序后的结果相同的字符串就是字母异位词。例如
"eat"和"tea"排序后都是"aet"。 - 时间复杂度：\(O(nk\log k)\)，其中 n 是字符串数量，k 是单个字符串的最大长度。排序每个字符串需要 \(O(k\log k)\)，共 n 个字符串。
- 空间复杂度：\(O(nk)\)，用于存储哈希表和结果。
2. 字符计数法（更优时间复杂度）
- 核心逻辑：统计每个字符串中 26 个字母的出现次数，用一个包含计数的字符串作为哈希表的键。例如
"eat"的计数是a:1, e:1, t:1，可以表示为"1#0#0#...#1#1"。 - 时间复杂度：\(O(nk)\)，统计每个字符串的字符计数只需 \(O(k)\)，共 n 个字符串。
- 空间复杂度：\(O(nk)\)，用于存储哈希表和结果。
🚀 完整代码实现
排序法（AC 代码）
cpp
#include <vector> #include <string> #include <unordered_map> #include <algorithm> using namespace std; class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 哈希表：键为排序后的字符串，值为对应的字母异位词列表 unordered_map<string, vector<string>> groups; for (string& s : strs) { string sorted_s = s; // 排序字符串，得到统一标识 sort(sorted_s.begin(), sorted_s.end()); // 将原字符串加入对应分组 groups[sorted_s].push_back(s); } // 将哈希表中的值转移到结果中 vector<vector<string>> result; result.reserve(groups.size()); // 预分配空间，提升效率 for (auto& [_, group] : groups) { result.push_back(move(group)); // 使用move避免拷贝 } return result; } };字符计数法（更优时间复杂度）
cpp
#include <vector> #include <string> #include <unordered_map> using namespace std; class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> groups; for (string& s : strs) { // 统计26个字母的出现次数 vector<int> count(26, 0); for (char c : s) { count[c - 'a']++; } // 将计数转换为字符串作为键 string key; for (int i = 0; i < 26; ++i) { key += to_string(count[i]) + '#'; } groups[key].push_back(s); } vector<vector<string>> result; for (auto& [_, group] : groups) { result.push_back(move(group)); } return result; } };📝 关键细节解析
结构化绑定
auto& [_, group]这是 C++17 引入的语法，用于遍历哈希表时直接提取键值对。_作为占位符表示我们不需要使用键，group直接引用值（字母异位词列表），避免了拷贝，提升了效率。reserve预分配空间在创建结果vector时，调用reserve(groups.size())可以提前分配足够的内存，避免后续push_back时频繁扩容，从而提升性能。std::move避免拷贝在将哈希表中的vector转移到结果时，使用std::move可以将vector的所有权直接转移，而不是进行昂贵的深拷贝。
🧪 测试用例验证
以题目示例输入strs = ["eat","tea","tan","ate","nat","bat"]为例：
- 排序法中，
"eat"、"tea"、"ate"排序后均为"aet"，会被分到同一组。 - 字符计数法中，它们的字符计数完全相同，也会被分到同一组。最终输出：
[["bat"],["nat","tan"],["ate","eat","tea"]]，与题目要求一致。
)
)
