题目
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""] 输出: [[""]]
示例 3:
输入: strs = ["a"] 输出: [["a"]]
解题
方法一：排序+哈希
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string>> mp; for(int i=0;i<strs.size();i++){ string s=strs[i]; sort(s.begin(),s.end()); mp[s].push_back(strs[i]); } vector<vector<string>> res; for(auto it:mp){ res.push_back(it.second); } return res; } };
方法二：质数
用质数表示26个字母，把字符串的各个字母相乘，这样可保证字母异位词的乘积必定是相等的
class Solution { public: const int MOD=1e9+7;//由于会溢出，因此取余 vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<int> hash={ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101 }; unordered_map<uint64_t,vector<string>> mp; for(string s:strs){ uint64_t num=1; for(char c:s){ num=num*hash[c-'a']%MOD; } mp[num].push_back(s); } vector<vector<string>> res; for(auto it:mp){ res.push_back(it.second); } return res; } };
