LeetCode 49. 字母异位词分组 C++ 哈希表解法

题目

完整代码

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 函数，作用是在动态数组末尾添加新元素，自动扩容。