Group Anagrams - Java Solution, no sorting - using prime hash code


  • 1
    V
    public class Solution {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        
        /* Instead of sorting, use a good hash function */
        public List<List<String>> groupAnagrams(String[] strs) {
            List<List<String>> res = new LinkedList<List<String>>();
            Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
            int mask, index = 0;
    
            for(String s: strs) {
                mask = 1;
                for(int i=0; i<s.length(); i++) mask *= primes[s.charAt(i)-'a'];
                
                if( !hash.containsKey(mask) ) {
                    res.add( new LinkedList<String>() );
                    hash.put(mask, index++);
                }
                res.get(hash.get(mask)).add(s);
            }
            return res;
        }
    

Log in to reply
 

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