LeetCode Hot100（2.字母异位词分组）

2.字母异位词分组题目给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。示例 1:输入:strs [eat, tea, tan, ate, nat, bat]输出:[[bat],[nat,tan],[ate,eat,tea]]解释在 strs 中没有字符串可以通过重新排列来形成bat。字符串nat和tan是字母异位词因为它们可以重新排列以形成彼此。字符串ateeat和tea是字母异位词因为它们可以重新排列以形成彼此。示例 2:输入:strs []输出:[[]]示例 3:输入:strs [a]输出:[[a]]提示1 strs.length 1040 strs[i].length 100strs[i]仅包含小写字母解法一排序思路首先要知道如何判断两个词是字母异位词通过观察可以看到两个字母异位词的字母都是一样的因此两个字母异位词通过sort()函数进行排列后的字符串是一样的。将排列后的字符串作为键其特征对应的字符串则作为值存入到哈希表中最后输出。代码class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring,vectorstring mp; for(string str:strs){ string key str; sort(key.begin(),key.end()); mp[key].emplace_back(str); } vectorvectorstring ans; for(auto it mp.begin();it !mp.end();it){ ans.emplace_back(it-second); } return ans; } };注意emplace_back()它是std::vector的成员函数用于在容器尾部添加元素。与push_back()的区别push_back()需要先构造对象再将其拷贝或移动到容器中而emplace_back()直接在容器尾部的内存位置原地构造对象避免了额外的拷贝或移动操作。在算法题中当向vector中插入复杂对象如string、自定义结构体时使用emplace_back()通常比push_back()性能更好解法二计数由于互为字母异位词的两个字符串包含的字母相同因此两个字符串中的相同字母出现的次数一定是相同的故可以将每个字母出现的次数使用字符串表示作为哈希表的键。由于字符串只包含小写字母因此对于每个字符串可以使用长度为 26 的数组记录每个字母出现的次数。需要注意的是在使用数组作为哈希表的键时不同语言的支持程度不同因此不同语言的实现方式也不同。代码// 定义 lambda 表达式作为自定义哈希函数用于计算 arrayint, 26 的哈希值 auto arrayHash [fn hashint{}] (const arrayint, 26 arr) - size_t { // 使用 accumulate 遍历数组通过左移和异或操作组合每个元素的哈希值 return accumulate(arr.begin(), arr.end(), 0u, [](size_t acc, int num) { return (acc 1) ^ fn(num); }); }; // 声明哈希表键为字母频次数组值为字符串向量。传入初始桶数 0 和自定义哈希函数 unordered_maparrayint, 26, vectorstring, decltype(arrayHash) mp(0, arrayHash); for (string str: strs) { arrayint, 26 counts{}; // 初始化长度为 26 的数组用于统计字母频次 int length str.length(); for (int i 0; i length; i) { counts[str[i] - a] ; // 将字符映射到 0-25 索引并累加频次 } mp[counts].emplace_back(str); // 以频次数组为键将当前字符串加入对应的列表中 } vectorvectorstring ans; // 初始化结果数组 for (auto it mp.begin(); it ! mp.end(); it) { ans.emplace_back(it-second); // 遍历哈希表将每个分组值加入结果数组 } return ans; // 返回最终的分组结果