49. Group Anagrams
Given an array of strings, group anagrams together.
For example, given: ```[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]``, Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: All inputs will be in lower-case.
这道题需要我们对给出的一组混杂在一起的变位词进行分类，分类的依据是:如果一个词进行变位之后，其对应的变位词存在于给定的向量中，则将这两个词加入新向量的一个分量里，如果还有，则追加入该分量中。
看起来是一道很麻烦的题，最初我考虑以某一个词为标准，列出其组成字母的全排列，然后再与后面的词进行对比。这个方法的难点就在于如何写出全排列，于是这个思路受阻，开始从别的方向考虑。
我们发现互为变位词的若干个词有一个相似之处，就是在经过排序之后完全相同，那么这样我们可以利用这个性质，让排序后的字符串作为主键，让这几个词组成的集合成为主键映射的值。
之后我们遍历哈希表，将主键相同的成员放入同一个分量即可，代码如下:
因为题目中说明只需要考虑小写字母即可，所以为加快排序速度我采用计数排序而不是库函数中的排序算法
/*version 1.0*/
class Solution {
private:
string strSort(string& str){
int count[26]={0},p=0,size=str.size();
string res(size,'a');
for(int i=0;i<str.size();i++)
count[str[i]-'a']++;
for(int i=0;i<26;i++)
for(int j=0;j<count[i];j++)
res[p++]+=i;
return res;
}
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
if(strs.empty())
return {};
unordered_map<string,vector<string>> hash;
vector<vector<string>> anagrams;
for(string s:strs){
string t=strSort(s);
// sort(t.begin(),t.end());
hash[t].push_back(s);
}
for(unordered_map<string,vector<string>>::iterator pos=hash.begin();pos!=hash.end();pos++){
vector<string> anagram(pos->second.begin(),pos->second.end());
anagrams.push_back(anagram);
}
return anagrams;
}
};
但这里返回的结果和答案在顺序上有一定的差别，仔细看了一下发现答案要求要按首字母从前向后的关系来排列，所以为了维护这样的顺序，我们采用multiset来存储主键相同的元素，而不再使用vector，因为multiset本身内部会使元素有序，所以我们只需利用这一性质即可。
代码如下:
/*version 2.0*/
class Solution {
private:
string strSort(string& str){
int count[26]={0},p=0,size=str.size();
string res(size,'a');
for(int i=0;i<str.size();i++)
count[str[i]-'a']++;
for(int i=0;i<26;i++)
for(int j=0;j<count[i];j++)
res[p++]+=i;
return res;
}
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
if(strs.empty())
return {};
unordered_map<string,multiset<string>> hash;
vector<vector<string>> anagrams;
for(string s:strs){
string t=strSort(s);
// sort(t.begin(),t.end());
hash[t].insert(s);
}
for(unordered_map<string,multiset<string>>::iterator pos=hash.begin();pos!=hash.end();pos++){
vector<string> anagram(pos->second.begin(),pos->second.end());
anagrams.push_back(anagram);
}
return anagrams;
}
};
非常有意思的一道题，值得我反复琢磨。
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。