题目
完整代码
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, vector<string>> hash;
for(auto& i:strs) {
string count(26,0);
for(auto& j:i) {
count[j-'a']+=1;
}
hash[count].push_back(i);
}
for(auto& k:hash) res.push_back(k.second);
return res;
}
};
详细思路
首先遍历输入的数组，对于其中出现的每个词语，我们都为其建立一个专属的长度为 26 的字符串，用来统计该字符串中每个字母出现的频次。该字符串初始化为全零（共 26 个零），从左到右依次代表字母 a 到 z 出现的频率。
例如 "abc" 对应的字符串为 11100000000000000000000000，同样的 "acb" 对应的字符串其实也是 11100000000000000000000000。为防止混淆，下文称其为'特征码'，我们可以利用这特性把字符异位词分类在一起。
具体操作是：遍历数组中的每个字符串，统计其出现各个字母的频率并写出对应的特征码，并将特征码相同的字符串放在一个数组中。创建哈希表 hash 来进行储存，特征码为键，字符串数组对应的为值。
| 特征码 | 字符串组 |
|---|---|
| 11100000000000000000000000 | "abc" "acb" |
| 10110000000000000000000000 | "acd" "dca" |
| ... | ... |
为了将例如 "acb","abc" 这些字符串以数组的形式合在一起，我们使用 push_back 函数，作用是在动态数组末尾添加新元素，自动扩容。
根据 push_back 的特性，我们最终输出结果仍然采用该函数。
这里有一部分需要注意：
for(auto& k:hash) res.push_back(k.second);
我们使用 k 遍历哈希表的每一个元素（每一个键值对代表一个元素），first 对应的是键，即上文图表中的特征码，second 对应的是值，正是结果需要的，因此我们将每一个元素的 second 连接在一起输出，最终返回 res。
代码逐行解析
vector<vector<string>> res; // 存储最终输出结果的动态数组
unordered_map<string, vector<string>> hash; // 创建哈希表，用来存储特征码和对应的字符串
for(auto& i:strs) // 遍历输入的字符数组
{
string count(26,0); // 对于其中出现的每个字符串，为其创建特征码并初始化
for(auto& j:i) // 遍历特征码中的每一个元素
{
count[j-'a']+=1; // 如果该元素出现，其对应的索引值的数字加一，例如如果出现'd'，其对应的 ascii 码减去'a'对应的 ascii 码为 3(即得到其在字母表中的偏移量），那么对应索引值为 3 的位置加一
}
hash[count].push_back(i); // 把特征码（键）相同的字符串放在一个值里
}
for(auto& k:hash) // 遍历哈希表的每个元素
res.push_back(k.second); // 将每个键值对中的值写入 res 数组中
return res; // 返回得到结果
其他小细节
for(auto& i:strs)
auto 是让编译器自动推断 i 的类型，& 代表引用，避免整个拷贝字符串，提高效率。这段代码意思是遍历 strs 的每一个字符串元素，并把当前遍历到的字符赋值给变量 i。
string count(26,0)
创建了一个长度为 26 的字符串，每个位置的初始值均为 0，该字符串命名为 count。