字母异位词分组算法实现

"字母异位词分组问题的算法解析与实现" 在编程和算法领域，字母异位词分组是一个常见的面试题，它涉及到字符串处理和哈希表的应用。本题目的目标是将给定的字符串数组按照字母异位词的规则进行分组，即将字母相同但排列不同的字符串放在一起。例如，给定输入字符串数组`["eat","tea","tan","ate","nat","bat"]`，期望的输出是`[["ate","eat","tea"],["nat","tan"],["bat"]]`。 这个问题可以通过以下步骤解决： 1. **定义关键字符串**：对于每个输入字符串，首先将其字母排序，得到一个“关键字符串”，作为这个字符串的标识。由于字母异位词的字母种类和数量是相同的，所以排序后的字符串可以唯一地代表原字符串。 2. **使用哈希表**：利用`unordered_map`（在C++中）或其他等效的数据结构，以关键字符串为键（key），原始字符串为值（value）存储每个字符串。这样，具有相同关键字符串的原始字符串将被存储在同一个桶（bucket）中。 3. **遍历并添加到哈希表**：对于输入数组中的每个字符串，首先排序字符串，然后用排序后的字符串作为键查询哈希表。如果该键已存在，将原始字符串添加到对应的值（字符串列表）中；如果不存在，则创建一个新的键值对。 4. **构建结果**：最后，遍历哈希表，将每个桶中的字符串列表添加到结果数组中，即可得到分组后的字母异位词。 以下是参考答案的C++代码实现： ```c++ #include <vector> #include <string> #include <algorithm> #include <unordered_map> 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; } }; ``` 这段代码展示了如何高效地解决字母异位词分组的问题，其时间复杂度主要取决于排序操作，为O(n * m log m)，其中n是字符串数组的大小，m是平均字符串长度。空间复杂度为O(n * m)，因为我们需要存储所有的字符串。注意，这里我们没有考虑答案的输出顺序，因为题目中明确指出不考虑顺序。