49 字母异位词分组
本题本质上是对哈希函数的考察
如何设计哈希函数,让字母异位词指向同一个key值,通过value值将这些字母异位词收集起来
由以上分析,我们判断使用unordered_map
做法一
第一种做法:对字符串进行排序,同一组异位词排序后的结果一定相同
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// 每个排序后的key对应的乱序的str
unordered_map<string, vector<string>> hashMap;
for (string& str : strs) {
string key = str;
sort(key.begin(), key.end());
hashMap[key].push_back(str);
}
vector<vector<string>> ans;
for (auto it = hashMap.begin(); it != hashMap.end(); it++) {
ans.push_back(it->second);
}
return ans;
}
};
做法二
第二种做法:同一组异位词每个字符出现的次数一定相同
例如"abca"
key的设置为a2b1c1
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (string str : strs) {
// 如果写成int counts[26];过不了
// 可能是因为编译优化
int counts[26] = {0};
for (char c : str) {
counts[c - 'a']++;
}
string key = "";
for (int i = 0; i < 26; ++i) {
if (counts[i]) {
key.push_back(i + 'a');
// 这一步不能漏
key.push_back(counts[i]);
}
}
map[key].push_back(str);
}
vector<vector<string>> res;
for (auto it = map.begin(); it != map.end(); it++) {
res.push_back(it->second);
}
return res;
}
};