49.字母异位词分组
题目:
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
1
2
3
4
5
6
7输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]说明:
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。思路:
字母相同,排序不同,那么只要我的哈希函数与字符串的字母顺序无关,也就是说所有字母异位词的哈希值相等,那么遍历输入做一次映射,再遍历map就可以了。a~z的ascii码为61~7A,即十进制的97~122,题解中相同思路为:为26个小写字母映射到26个质数,string的哈希值为每个字母对应质数之积。但这么做会导致哈希值很大。但是!!!重新考虑问题,题目为==字母异位词==分组,不会出现很长的词,而且还可以按照字母出现频率由小到大匹配质数。实现:
- 关键点一:用户定义哈希函数
- 关键点二:映射
- 关键点三:遍历哈希表
- 难点:如何找到不会溢出的符合条件的哈希函数?
- 时间复杂度
O(N)
,空间复杂度O(N)
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int primes[26] = {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};
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<int, vector<string>> ans;
for(auto str:strs){
unsigned long key = 1;
for(auto c:str){
key *= primes[c-'a'];
}
ans[key].emplace_back(str);
}
vector<vector<string>> res;
for(auto m:ans)
res.emplace_back(m.second);
return res;
}
};问题在于实质上在存入无序关联容器的时候还是使用了默认哈希函数(ul类型),这样会降低性能,而直接重载unordered_map的哈希函数一直无法通过编译,后续再思考原因…耗了一晚上。
其他解法:
- 排序每个string,排序后的string作为key
- key为每个字母出现次数的编码