LeetCode 49. 字母异位词分组 —— 哈希表解法详解

一、题目描述题目链接给定一个字符串数组strs将所有字母异位词组合在一起可以按任意顺序返回结果列表。字母异位词字母种类和每个字母出现次数完全相同仅排列顺序不同的字符串。示例输入: strs [eat, tea, tan, ate, nat, bat] 输出: [[eat,tea,ate], [tan,nat], [bat]]二、解题思路2.1 核心难点判断两个字符串是否互为异位词不能直接比较字符串本身顺序不同。需要找到一种统一的标识使得互为异位词的字符串拥有相同的标识。2.2 关键洞察由于异位词的字母组成完全相同对字符串排序后结果必然一致。原字符串排序后标识 Keyeat/tea/ateaettan/natantbatabt因此可以将排序后的字符串作为哈希表的 Key原始字符串作为 Value 存入同一组。2.3 算法流程创建一个哈希表mpKey 为排序后的字符串Value 为属于该组的原始字符串数组。遍历strs对每个字符串复制一份并排序得到 Key。将原字符串追加到mp[Key]对应的数组中。遍历哈希表将所有 Value 收集到结果数组返回。三、C 代码实现#include vector #include string #include unordered_map #include algorithm using namespace std; class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { // 哈希表Key 排序后的字符串Value 该组的所有原始字符串 unordered_mapstring, vectorstring mp; // 传统 for 循环遍历字符串数组 for (int i 0; i strs.size(); i) { string key strs[i]; // 复制一份作为 Key 的原始数据 sort(key.begin(), key.end()); // 排序生成身份证 mp[key].push_back(strs[i]); // 按 Key 分组存入 } // 传统迭代器遍历哈希表收集结果 vectorvectorstring result; for (auto it mp.begin(); it ! mp.end(); it) { result.push_back(it-second); } return result; } };四、哈希表相关知识详解4.1 什么是哈希表哈希表Hash Table是一种通过键Key直接访问值Value的数据结构平均查找、插入、删除的时间复杂度为O(1)。C 中对应的容器是unordered_map底层使用哈希桶实现。4.2unordered_map常用操作操作语法说明声明unordered_mapK, V mp;K 为键类型V 为值类型插入/访问mp[key] value;Key 不存在时自动创建Value 使用默认值追加元素mp[key].push_back(x);常用于 Value 是 vector 的场景查找mp.find(key)返回迭代器未找到返回mp.end()判断存在mp.count(key)返回 0 或 1大小mp.size()返回键值对数量遍历for (auto it mp.begin(); it ! mp.end(); it)迭代器遍历4.3 本题用到的关键操作①mp[key].push_back(strs[i]);这一行包含两个动作若key不存在unordered_map会自动创建keyValue 为默认构造的空vectorstring。然后调用push_back将strs[i]追加进去。等价于if (mp.find(key) mp.end()) { mp[key] vectorstring(); } mp[key].push_back(strs[i]);使用mp[key]更加简洁但需要注意如果只是想判断 key 是否存在应使用find或count避免无意中创建空条目。4.4pair与迭代器遍历unordered_map时迭代器指向的元素类型为pairconst string, vectorstringit-firstKey排序后的字符串it-secondValue原始字符串数组五、复杂度分析设N为字符串数量K为字符串最大长度。维度复杂度说明时间O(N × K log K)每个字符串排序耗时 O(K log K)哈希操作为 O(1)空间O(N × K)需存储所有字符串六、拓展计数法优化当字符串很长时排序的O(K log K)会成为瓶颈。可用字符计数替代排序将时间复杂度降至O(N × K)。思路用一个长度为 26 的数组统计每个字母出现次数转换为字符串作为 Key。string getKey(const string s) { int count[26] {0}; for (int i 0; i s.size(); i) { count[s[i] - a]; } string key; for (int i 0; i 26; i) { key to_string(count[i]) #; // 用 # 分隔避免歧义 } return key; }将主循环中的sort(key.begin(), key.end())替换为key getKey(strs[i])即可。