题目来源

• leetcode：group-anagrams

题目描述

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

    }
};

题目解析

这应该是一个简单题目，关键在于理解题意。题目要求给使用了相同字符的单词进行分组。

也就是说如果两个字符串所含字符种类一样，每个字符所含个数一样，那么就是一类。问整个字符数组中有几类

比如对于例子一：

我们可以将字符串数组中的每个字符串排序，然后两两进行比较，如果返回true，表示是就可以分为一类

哈希解法一

1. 准备几个bucket，用于存放分组后的原字符串

2. 根据排序后的字符串，找到所属的bucket，将原字符串放入bucket

3. 符串数组遍历结束后，就完成了分组

将每个bucket中的子结果集放到最终的结果集中

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int len = strs.size();
        vector<vector<string>> ans;
        std::map<std::string, vector<string>> hash;

        for (int i = 0; i < len; ++i) {
            std::string key = strs[i];
            std::sort(key.begin(), key.end());
            hash[key].push_back(strs[i]);
        }
        
        for(auto &it : hash){
            ans.push_back(it.second);
        }
        return ans;
    }
};

哈希解法二

可以统计每个字符串里a几个，b几个…，生成一个字符串代表一类，然后放到哈希表中去重

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::map<std::string, std::vector<std::string>> map;
        for(auto str : strs){
            int record [26] = {0};
            for(char ch : str){
                record[ch - 'a']++;
            }
            
            std::string key;
            for(int v : record){
                key.append(std::to_string(v)).append("_");
            }
            map[key].emplace_back(str);
        }

        vector<vector<string>> ans;
        for(const auto& l : map){
            ans.emplace_back(l.second);
        }
        return ans;
    }
};

类似题目