题目
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
解题
方法一：排序
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string>> map; for(string& str:strs){ string key=str; sort(key.begin(),key.end()); map[key].push_back(str); } vector<vector<string>> res; for(auto&[_,v]:map){ res.push_back(v); } return res; } };
方法二：哈希表(自定义哈希函数)
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 自定义对 array<int, 26> 类型的哈希函数 auto arrayHash=[fn=hash<int>{}](const array<int,26>& arr)->size_t{ return accumulate(arr.begin(),arr.end(),0u,[&](size_t acc,int num){ return (acc<<1)^fn(num); }); }; unordered_map<array<int,26>,vector<string>,decltype(arrayHash)> map(0,arrayHash); for(string& str:strs){ array<int,26> tmp{};//一定要加括号，才会初始化元素都为0，否则元素是乱的。 for(char c:str){ tmp[c-'a']++; } map[tmp].push_back(str); } vector<vector<string>> res; for(auto it=map.begin();it!=map.end();it++){ res.push_back(it->second); } return res; } };
补充：
上面定义哈希函数其实是嵌套了两个lambda函数,下面这样看会清晰点
auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t { return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) { return (acc << 1) ^ fn(num); }); };
其中[fn = hash{}]是初始化捕获列表,也就是说定义了一个auto fn = hash{};供后续使用
默认是使用hash 来实现的，但是没有办法去实现一个array，因此需要手动去构造一个哈希函数。本次构造哈希函数，是基于已有的hash去实现的，因此哈希碰撞概率几乎为0，因此无需自定义判断函数。
这是unordered_map的构造，我们可以在unordered_map文档查看定义的模板类型，并在unordered_map构造函数文档查看构造函数的参数。
unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> map(0, arrayHash);
其他定义哈希函数的方式：
1.仿函数
用class实现
主要函数名后面要加const
class arrayHash{ public: size_t operator()(const array<int,26>& arr) const{ hash<int> fn; return accumulate(arr.begin(),arr.end(),0u,[&](size_t acc,int num){ return (acc<<1)^fn(num); }); } }; unordered_map<array<int,26>,vector<string>,arrayHash> map(0,arrayHash());//arrayHash是一个类,arrayHash()是一个函数名(仿函数)
用struct实现
可以调用无参构造函数，因为传入了类，并且重载了方法。但是之前用lambda函数实现的decltype(…)必须调用有参构造函数，因为传入的只有一个类型，我们还需要对该类型函数进行实现的补充。
struct arrayHash{ size_t operator()(const array<int,26>& arr) const{ hash<int> fn; return accumulate(arr.begin(),arr.end(),0u,[&](size_t acc,int num){ return (acc<<1)^fn(num); }); } }; unordered_map<array<int,26>,vector<string>,arrayHash> map;
2.静态函数
定义一个自定义静态函数
static size_t arrayHash(const array<int,26>& arr){ return accumulate(arr.begin(),arr.end(),0u,[&,fn=hash<int>{}](size_t acc,int num){ return (acc<<1)^fn(num); }); }
注意要加取址符号，并获得类型。 注意要调用有参构造函数。
unordered_map<array<int,26>,vector<string>,decltype(&arrayHash)> map(0,arrayHash);
参考链接
C语言中的0U或1U是什么意思?其中0U表示无符号整型0
array用法 array是定长数组，而vector是可变长数组
方法三：哈希表简洁写法
既然unordered_map默认没有 array或者vector作为键，那么转变思路，直接用string来作为哈希键。
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector <vector<string>> ans; unordered_map <string, vector<string>> ss; for(auto &str : strs) { string s = string(26, '0'); for(auto &c : str) s[c - 'a']++; ss[s].emplace_back(str); } for(auto &c : ss) ans.emplace_back(c.second); return ans; } };
