使用散列查找anagram组并将字母表映射为随机数
使用散列查找anagram组并将字母表映射为随机数
提问于 2022-08-28 05:52:47
我在用leetcode解决小组的Anagram问题。问题https://leetcode.com/problems/group-anagrams/的链接
下面是我写的代码
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& inp) {
if(inp.size() == 0)
return vector<vector<string> > {{}};
int count = 1;
map<char, long long> alphaVal;
for (char i = 'a'; i <= 'z'; i++) {
alphaVal[i] = int(rand());
}
map<long long, vector<string> > prep;
for (auto value : inp) {
long long temp = 0;
for (auto c_p : value) {
temp += alphaVal[c_p];
}
//cout << "temp " << temp << endl;
prep[temp].push_back(value);
}
vector < vector<string> > ans;
for (auto it = prep.begin(); it != prep.end(); it++) {
vector<string> temp;
for (int i = 0; i < it->second.size(); i++) {
//cout << it->second[i] << " ";
temp.push_back(it->second[i]);
}
ans.push_back(temp);
}
return ans;
}
};我有两个问题：
- 即使上面的解决方案有效，随机使用真的是一个好主意吗？
- 在此之前，我编写了一个逻辑来检查字符并存储字符串。map，vector > prep；for (auto : inp) { set temp；for (autoc_p: value) { temp.insert( c_p )；}prep临时.push_back(值)；}
对于上述逻辑，有一个测试用例失败
ip: ["ddddddddddg","dgggggggggg"]
op: [["ddddddddddg","dgggggggggg"]]尽管这两个字符串是唯一的，但set哈希计算表明它是相同的。知道为什么在所选的测试用例上出现这种行为吗？只是好奇地想知道。谢谢你的回答！
回答 1
Code Review用户
回答已采纳
发布于 2022-08-28 06:37:56
回答你的问题
即使上面的解决方案有效，随机使用真的是一个好主意吗？
这不是个好主意。它不能保证一个正确的结果。要在较高级别上解释代码：
- 将随机的
long long值赋给字母表 - 对于输入中的每个单词
- 字母的随机值之和
- 由于字谜将具有相同的和，所以将单词按和分组。
这种做法存在缺陷，因为：
- 不是字谜的词也可能有相同的和。由于随机性带来的一些坏运气，单词可能会被错误地分配到同一个桶中。
- 虽然
long long是一个很大的范围，但可能不止一个字母被分配相同的随机数。这将大大增加碰撞的风险。
要正确地分组字谜，分组键必须清楚地标识字谜，并且不能被不应该在同一组中的单词所共享。这个独特的键可以是字母计数的地图：
map<map<char, int>, vector<string>> counts2words;
for (auto word : words) {
map<char, int> counts;
for (auto c : word) {
counts[c]++;
}
counts2words[counts].push_back(word);
}尽管这两个字符串是唯一的，但set哈希计算表明它是相同的。知道为什么在所选的测试用例上出现这种行为吗？
首先，这一说法具有误导性。在这个例子中，比散列计算更多的是相同的，这里两个集合本身是相同的，由字母"d“和"g”组成。
但是让我们假设两个字符串S1和S2的哈希计算是相同的。这并不奇怪，这就是散列函数的工作方式。冲突会发生，这就是为什么在处理散列时，当哈希值相等时，您还必须比较未散列的值，以验证它们是否真的相等。
使用描述性名称
整个实现过程中使用的名称都很神秘。参见上面的示例代码，其中我使用了一个计数图:所有东西都有一个描述性名称，除了字母的琐碎的c。
删除不必要的输入验证
这是不必要的：
如果(inp.size() == 0)返回vector >{{}；
首先，问题描述保证输入绝不是空的。
另一方面，实现自然地正确处理空输入的情况。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/279220
复制相关文章
相似问题
腾讯云开发者
