哈希表巧解字母异位词分组：从思路到实现的全方位讲解

在本题中，我们需要将一组字符串按照字母异位词进行分组。字母异位词是由相同字母组成的单词，只是字母排列顺序不同。例如 “eat” 和 “tea” 是字母异位词，因为它们的字母组成完全相同。

题目链接：49. 字母异位词分组 - 力扣（LeetCode）

解题思路

为了分组字母异位词，我们需要找到一种方法，能够识别出字母异位词之间的共同特征。对同一个字母异位词组中的所有单词，我们可以通过以下方法找到它们的特征。

方法 1：字符串排序法

字母异位词的一个明显特征是，它们都包含相同的字母，且每个字母的出现次数相同。因此，如果我们将每个单词的字母排序，那么字母异位词的排序结果是一样的。

比如对于单词列表 ["eat", "tea", "tan", "ate", "nat", "bat"]，我们可以将每个单词按字母顺序排序：

eat 排序后变为 aet
tea 排序后变为 aet
tan 排序后变为 ant
ate 排序后变为 aet
nat 排序后变为 ant
bat 排序后变为 abt

我们发现 "eat"、"tea" 和 "ate" 排序后都是 "aet"，所以它们是字母异位词，可以分为一组。同样 "tan" 和 "nat" 排序后都是 "ant"，可以分为另一组。

实现步骤

使用一个 unordered_map，其中键为排序后的字符串，值为一个 vector，用来存储属于该组的字母异位词。
遍历每个字符串，将其排序，然后将排序后的字符串作为键，原始字符串作为值，添加到 unordered_map 中对应的组。
最后，将 unordered_map 中的所有值（即字母异位词组）提取出来，组成最终的结果列表。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>class Solution {
public:std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {std::unordered_map<std::string, std::vector<std::string>> anagramMap;// 遍历每个字符串for (const std::string& str : strs) {std::string sorted_str = str;  // 复制字符串std::sort(sorted_str.begin(), sorted_str.end());  // 排序字符串anagramMap[sorted_str].push_back(str);  // 将原字符串放入排序后键的组中}// 将map中所有的值转换为结果格式std::vector<std::vector<std::string>> result;for (const auto& pair : anagramMap) {result.push_back(pair.second);}return result;}
};

示例与解释

我们来看一个示例输入 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]：

首先，遍历每个字符串并排序：
- eat 排序为 aet，tea 排序为 aet，ate 排序为 aet
- tan 排序为 ant，nat 排序为 ant
- bat 排序为 abt
按照排序后的字符串作为键，将字母异位词添加到 unordered_map：
- aet 对应的值为 ["eat", "tea", "ate"]
- ant 对应的值为 ["tan", "nat"]
- abt 对应的值为 ["bat"]
将 unordered_map 中的所有值（即每个字母异位词组）提取出来，组成结果：
- 结果为 [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

时间和空间复杂度分析

时间复杂度：O(N * K log K)，其中 N 是字符串的数量，K 是字符串的平均长度。排序每个字符串的复杂度是 O(K log K)。
空间复杂度：O(N * K)，用于存储所有字符串的分组。

方法 2：字符频次法

如果字符串较长，排序的效率会变低。我们可以采用另一种方法，用字符频次来表示每个字符串。

对于每个字符串，统计它包含的每个字母的次数，然后将字母频次数组作为该字符串的特征。例如：

eat 的频次数组是 [1, 1, 0, 0, ..., 1]，表示有 1 个 ‘a’、1 个 ‘e’、1 个 ‘t’。
tea 和 ate 的频次数组相同，因此它们是字母异位词。

实现步骤

对于每个字符串，计算它的字符频次数组，将频次数组转换为字符串作为键。
使用 unordered_map 将该键与字母异位词组对应起来。
最后，将字母异位词组提取出来，组成结果列表。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>class Solution {
public:std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {std::unordered_map<std::string, std::vector<std::string>> anagramMap;for (const std::string& str : strs) {std::vector<int> count(26, 0);  // 初始化26个字母的频次for (char c : str) {count[c - 'a']++;}std::string key;for (int freq : count) {key += "#" + std::to_string(freq);  // 将频次数组转换成键}anagramMap[key].push_back(str);  // 将原字符串添加到对应的组中}std::vector<std::vector<std::string>> result;for (const auto& pair : anagramMap) {result.push_back(pair.second);}return result;}
};

示例与解释

对于输入 ["eat", "tea", "tan", "ate", "nat", "bat"]：

首先，将每个字符串转换为频次数组：
- eat 的频次数组为 [1, 0, 0, ..., 1]，tea 和 ate 也相同。
- tan 和 nat 的频次数组相同，为 [1, 0, 0, ..., 1]。
- bat 的频次数组为 [1, 1, 0, ..., 1]。
使用频次数组字符串作为键，构建 unordered_map：
- 相同频次数组的字符串会分到同一个组中。
提取 unordered_map 的值，得到最终结果。