社区首页 >问答首页 >使用散列查找anagram组并将字母表映射为随机数

问使用散列查找anagram组并将字母表映射为随机数
EN

Code Review用户

提问于 2022-08-27 21:52:47

回答 1查看 143关注 0票数 2

我在用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哈希计算表明它是相同的。知道为什么在所选的测试用例上出现这种行为吗？只是好奇地想知道。谢谢你的回答！

c++

algorithm

strings

hash-map

回答 1

Code Review用户

回答已采纳

发布于 2022-08-27 22: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);
}