C++实现字母异位词分组的两种高效方法

1. 问题背景与核心思路字母异位词分组是LeetCode中经典的字符串处理问题要求将给定字符串数组中所有字母异位词组合在一起。字母异位词指的是字母相同但排列不同的单词比如eat、tea、ate就是一组字母异位词。这个问题的关键在于如何高效判断两个字符串是否为字母异位词。最直观的思路是对每个字符串进行排序排序后相同的字符串即为字母异位词。例如eat → aettea → aetate → aet2. C实现方案详解2.1 哈希表排序法这是最直接有效的解决方案时间复杂度为O(NKlogK)其中N是字符串数量K是字符串最大长度。#include vector #include string #include unordered_map #include algorithm using namespace std; vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring map; for (string s : strs) { string key s; sort(key.begin(), key.end()); map[key].push_back(s); } vectorvectorstring result; for (auto pair : map) { result.push_back(pair.second); } return result; }2.2 哈希表计数法对于包含非英文字符或超大字符集的情况可以使用计数法替代排序时间复杂度优化为O(NK)。vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring map; for (string s : strs) { 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]) #; } map[key].push_back(s); } vectorvectorstring result; for (auto pair : map) { result.push_back(pair.second); } return result; }3. 关键实现细节3.1 哈希表的选择使用unordered_map而非map平均时间复杂度O(1) vs O(logN)不需要按键排序更节省内存3.2 字符串处理优化对于排序法避免在原字符串上直接排序创建副本作为key小字符串排序比计数法更快对于计数法使用固定长度数组而非vector用#分隔计数避免冲突4. 复杂度分析方法时间复杂度空间复杂度排序法O(NKlogK)O(NK)计数法O(NK)O(NK)实际测试中当K较小时排序法更快当K较大或字符集复杂时计数法更优。5. 边界情况处理需要特别注意以下边界情况空输入返回空vector所有字符串相同返回单个分组无字母异位词每个字符串单独分组包含空字符串应单独分组6. 测试用例示例void test() { vectorstring case1 {eat,tea,tan,ate,nat,bat}; auto res1 groupAnagrams(case1); // 输出: [[bat],[nat,tan],[ate,eat,tea]] vectorstring case2 {}; auto res2 groupAnagrams(case2); // 输出: [[]] vectorstring case3 {a}; auto res3 groupAnagrams(case3); // 输出: [[a]] }7. 实际应用场景字母异位词分组算法在以下场景有实际应用文本分析发现相似词汇拼写检查建议正确拼写密码学分析字符频率生物信息学DNA序列分析8. 算法优化思考进一步优化方向并行处理多线程处理字符串分组预处理对常见前缀/后缀特殊处理哈希优化设计更高效的哈希函数9. 常见错误与调试常见错误包括忘记处理空字符串直接在原字符串上排序哈希表value类型错误计数法分隔符选择不当调试技巧打印中间key值单步调试观察哈希表变化添加边界测试用例10. 完整可提交代码class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring map; for (string s : strs) { string key s; sort(key.begin(), key.end()); map[key].push_back(s); } vectorvectorstring result; for (auto pair : map) { result.push_back(pair.second); } return result; } };这个实现已经通过LeetCode所有测试用例可以直接提交。对于追求更高性能的场景可以尝试改用计数法实现。