Can anyone think of a good and efficient hash function for anagrams??


  • 0
    M

    I scanned the discussions and found the most general idea is to use a map with keys hashed from the sorted word. On one hand sort each word is not efficient. On the other hand Java string's hash function seems too strong only to distinguish anagrams.

    So I'm thinking is there an efficient hash function that guarantees all anagrams would be hashed the same? ( Maybe this problem is already being studied by many CS genius, if anyone could think of a perfect solution and prove it, you can write a paper and get it published !)


  • 0
    C

    Not perfect, but at least linear. Works only if you know the range of you characters.

    int[] countChars = new int[26];
    for (char c : s.toCharArray()) {
        ++countChars[c - 97];
    }
    String key = Arrays.toString(countChars);
    

    I also thought about assigning each char a prime. And then simply multiply them.


Log in to reply
 

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