My favorite coding question solution

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;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *