I recently got asked on one question in leetcode, this is my favorite solution for all kind of coding questions, because it tries to hash the string into the root of a polynomial equation, and restrict it into a prime modular field. It utilizes basic math theorem, the number representation in the computer, and Vieta”s formulas.
Leetcode Link
Solution beats 99.80% in speed!
class Solution {
public:
string hash(string s)
{
unsigned char bigprime = 113;
int sz = s.length();
for (int i = 0; i < sz; ++i)
{
s[i] -= 96;
}
string result = s;
if (sz < 2)
{
return result;
}
for (int i = 1; i < sz; ++i)
{
int nextChar = (unsigned char)s[i];
int lastsum = (unsigned char)result[i - 1];
for (int j = i - 1; j >=0; --j)
{
if (j == 0)
{
result[j] = (((int)result[j] * nextChar) % bigprime);
}
else
{
result[j] = (((int)result[j] * nextChar + result[j - 1]) % bigprime);
}
}
auto val = ((lastsum + s[i]) % bigprime);
result[i] = val;
}
for (int i = 0; i < sz; ++i)
{
if (result[i] == 0)
{
result[i] = bigprime + 1;
}
}
return result;
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
std::unordered_map<string, vector<string>> maps;
for (int i = 0; i < strs.size(); ++i)
{
auto thishash = hash(strs[i]);
maps[thishash];
maps[thishash].push_back(strs[i]);
}
vector<vector<string>> result;
for (auto iter = maps.begin(); iter != maps.end(); ++iter)
{
result.emplace_back(std::move(iter->second));
}
return result;
}
};