class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string> > ans;
if (strs.empty()) {
return ans;
}
unordered_map<int, vector<string>> hash;
vector<int> primes{2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 107};
for (const string& str : strs) {
int getHash = 1;
for (int i = 0; i < (int)str.size(); i++) {
getHash *= primes[str[i] - 'a'];
}
if (hash[getHash].size()) {
hash[getHash].push_back(str);
} else {
hash[getHash] = vector<string>{str};
}
}
for (const auto& hashList : hash) {
if (hashList.second.size()) {
ans.push_back(hashList.second);
}
}
return ans;
}
};
Y2xhc3MgU29sdXRpb24gewogICAgCnB1YmxpYzoKICAgIHZlY3Rvcjx2ZWN0b3I8c3RyaW5nPj4gZ3JvdXBBbmFncmFtcyh2ZWN0b3I8c3RyaW5nPiYgc3RycykgewogICAgICAgIHZlY3Rvcjx2ZWN0b3I8c3RyaW5nPiA+IGFuczsKICAgICAgICBpZiAoc3Rycy5lbXB0eSgpKSB7CiAgICAgICAgICAgIHJldHVybiBhbnM7CiAgICAgICAgfQogICAgICAgIHVub3JkZXJlZF9tYXA8aW50LCB2ZWN0b3I8c3RyaW5nPj4gaGFzaDsKICAgICAgICB2ZWN0b3I8aW50PiBwcmltZXN7MiwgMywgNSwgNywgMTEsIDEzLCAxNywgMjMsIDI5LCAzMSwgMzcsIDQxLCA0MywgNDcsIDUzLCA1OSwgNjEsIDY3LCA3MSwgNzMsIDc5LCA4MywgODksIDk3LCAxMDEsIDEwN307CiAgICAgICAgZm9yIChjb25zdCBzdHJpbmcmIHN0ciA6IHN0cnMpIHsKICAgICAgICAgICAgaW50IGdldEhhc2ggPSAxOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IChpbnQpc3RyLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgICAgICBnZXRIYXNoICo9IHByaW1lc1tzdHJbaV0gLSAnYSddOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmIChoYXNoW2dldEhhc2hdLnNpemUoKSkgewogICAgICAgICAgICAgICAgaGFzaFtnZXRIYXNoXS5wdXNoX2JhY2soc3RyKTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGhhc2hbZ2V0SGFzaF0gPSB2ZWN0b3I8c3RyaW5nPntzdHJ9OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGZvciAoY29uc3QgYXV0byYgaGFzaExpc3QgOiBoYXNoKSB7CiAgICAgICAgICAgIGlmIChoYXNoTGlzdC5zZWNvbmQuc2l6ZSgpKSB7CiAgICAgICAgICAgICAgICBhbnMucHVzaF9iYWNrKGhhc2hMaXN0LnNlY29uZCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFuczsKICAgIH0KfTs=