More fun with Euler and Mersenne


  • 0

    Again using Euler and Mersenne primes, see here for some description/thoughts.

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<long, vector<string>> map;
        for (string str : strs)
            map[key(str)].push_back(str);
        vector<vector<string>> groups;
        for (const auto &group : map)
            groups.push_back(group.second);
        return groups;
    }
    
    long key(string s) {
        long result = 1;
        for (char c : s) {
            int n = c - 'a' + 1;
            result = result * (n*n + n + 41) % INT_MAX;
        }
        return result;
    }

  • 0
    A

    @StefanPochmann When using your own hash function, no matter how delicate, you have to provide collision detection and handling, otherwise we could always construct a testcase to make your solution fail.

    The built-in hashmap classes aren't that simple as only computing a key, the collision detetction and handlding, though hidden, is the essence of these classes.


  • 0

    @ayuanx Not sure why you're telling me that. I guess you didn't follow the link?


  • 0
    A

    @StefanPochmann Your key is at max INT_MAX, so if we just blindly generate INT_MAX + 1 different non-anagram strings, there is guaranteed to have at least one collision.


  • 0

    @ayuanx Yeah, I know. Still not sure why you're telling me this...


  • 0
    A

    @StefanPochmann Well, I was just saying when I saw it. No offence intended.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.