思路还是很容易想到的,肯定是哈希表转Vector数组,问题在哈希表的构建。简单方法是对每个单词排序后的string作为key,复杂一点的就是对字母计数然后构造哈希的key,但是c++自定义哈希还是挺难写的,记录一下。
排序解法
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
作者:力扣官方题解
链接:https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
计数构造哈希
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)> mp(0, arrayHash);
for (string& str: strs) {
array<int, 26> counts{};
int length = str.length();
for (int i = 0; i < length; ++i) {
counts[str[i] - 'a'] ++;
}
mp[counts].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
作者:力扣官方题解
链接:https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Comments 1 条评论
博主 匿名
一打开就看到更新lc,神清气爽:)