字母异位词分组，leetCode热题100，C++实现

题目来源：leetCode

49. 字母异位词分组 - 力扣（LeetCode）

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

解法1：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp;for (string& str: strs) {string key = str;sort(key.begin(), key.end());mp[key].emplace_back(str);}vector<vector<string>> ans;for (auto it = mp.begin(); it != mp.end(); ++it) {ans.emplace_back(it->second);}return ans;}
};

排序，意思是将每一个单词都进行排序，比如eat排序后变成aet，tea排序后变成aet，然后把原来的单词放到aet这个key的value里

然后放入容器里返回即可

解法2

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {// 自定义对 array<int, 26> 类型的哈希函数auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {return (acc << 1) ^ fn(num);});};unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);for (string& str: strs) {array<int, 26> counts{};int length = str.length();for (int i = 0; i < length; ++i) {counts[str[i] - 'a'] ++;}mp[counts].emplace_back(str);}vector<vector<string>> ans;for (auto it = mp.begin(); it != mp.end(); ++it) {ans.emplace_back(it->second);}return ans;}
};

该方法使用的是计数法，比如eat里包含1个a，一个e和一个t，tea和ate也是一样的，然后我们把每一个拥有相同元素的单词放到一块

知道了思想后我们来解释一下代码

// 自定义对 array<int, 26> 类型的哈希函数auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {return (acc << 1) ^ fn(num);});};

首先是自定义的hash函数，用于计算hash值，这是一个lambda表达式，首先是捕获列表[fn = hash<int>{}]，其中hash<int>是C++标准库中定义的函数对象类，专门用于计算整数的哈希值，在 <functional> 头文件中定义，然后是参数列表(const array<int, 26>& arr)，是一个一维数组，可以存放26个元素（26个字母），然后是返回类型-> size_t

lambda和unordered_map都是C++11里新增的，以及这里的array也是，不清楚的可以看看我之前的博客

C++11-CSDN博客

C++-哈希Hash_c++ hash<int>-CSDN博客

{return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {return (acc << 1) ^ fn(num);});
}

然后是上面的函数体，使用 accumulate 算法遍历数组并计算组合哈希值，std::accumulate 是标准库算法，用于计算范围内元素的累积值。

accumulate(开始迭代器, 结束迭代器, 初始值, 累积函数)

里面的0u是初始值（无符号整数0），然后里面嵌套了一个lambda表达式，以引用的方式捕获外部变量（包括fn），使lambda内部可以使用外部的hash<int>对象，acc是积累值（上一次的计算结果），num是当前数组元素值（字母计数），接下来看函数体，acc<<1是左移1位，相当于乘以2，比如5<<1就是10，fn(num)是计算当前数字的哈希值，接着对他两进行异或混合

假设数组是arr=[1,2,3]，那么第一次迭代结果如下

第二次迭代结果如下

第三次迭代结果如下

为什么这么复杂？

因为我们需要位整个数组生成一个唯一的哈希值

为什么这里需要自定义哈希函数？

因为我们要使用array<int,26>作为哈希表的key，但是C++标准库里没有为这种自定义类型提供默认的哈希函数

// 这样写会编译错误！
unordered_map<array<int, 26>, vector<string>> mp; // ❌ 错误

自定义哈希函数的作用是告诉编译器如何计算哈希值，确保相同的计数产生相同的哈希值

array<int, 26> arr1 = {1,0,0,0,1,0,...,1,...}; // eat
array<int, 26> arr2 = {1,0,0,0,1,0,...,1,...}; // teaarrayHash(arr1) == arrayHash(arr2);  // true，相同的哈希值

array<int, 26> arr1 = {1,0,0,0,1,0,...,1,...}; // eat
array<int, 26> arr2 = {1,0,1,0,0,0,...,0,...}; // tanarrayHash(arr1) != arrayHash(arr2);  // true，不同的哈希值

以及不同的计数产生不同的哈希值

这里可以把哈希表想象成一个有很多抽屉的柜子，每个key都要被分配到一个特定的抽屉

哈希表柜子：
[抽屉0] → 存放key哈希值 % N = 0的元素
[抽屉1] → 存放key哈希值 % N = 1的元素  
...
[抽屉N-1] → 存放key哈希值 % N = N-1的元素

为什么需要哈希值？

用于快速定位key应该放到哪个抽屉里

比如我们用eat这个单词举例

字符串 "eat" 
    → 统计计数: array<int, 26> = {a:1, e:1, t:1, ...}
    → 计算哈希: arrayHash({1,0,0,0,1,0,...,1,...}) = 12345
    → 定位抽屉: 12345 % N = 抽屉5
    → 存储在抽屉5中

查找也是同理，这里是取模运算，N是哈希表中桶的数量，也就是抽屉总数

为什么需要取模？因为哈希值可能非常大，但是我们的抽屉数量是有限的，比如上面的哈希值为12345，非常大

然后我们看后续代码

unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);

我们创建一个map，key是array，26个整数的一维数组，存储字母频率，value是vector<string>，用于存储所有产生相同字母频率的原始字符串，decltype是哈希函数类型

array<int, 26> counts{};  // 所有26个元素初始化为0
for (int i = 0; i < length; ++i) {counts[str[i] - 'a']++;  // 统计每个字母出现次数
}

这段代码用于统计每个单词的字母频率，然后通过emplace_back将原本单词放入到key为counts的位置，我们用eat举例

counts = [a:1, e:1, t:1, 其他:0]  // 字母频率数组
mp[counts] // 查找或创建对应这个频率的分组
→ 将 "eat" 加入分组 ["eat"]

我们可以发现有相同字母频率的单词会被放到一个key对应的value里，而value是一个vector

最后我们再通过和解法1一样的办法，把单词放入容器里返回即可