Grouping an array of strings into anagrams This program takes an arbitrary array of strings and group anagrams into arrays and return them in a array. Any string without any anagrams is still put in an array.

This code works perfectly and I would appreciate any comments on making this more efficient in terms of computation time.

import java.util.Arrays;
import java.util.HashMap;
import java.util.ArrayList;

public class AnagramSort{

    public static void main( String[] args ){
        HashMap&lt; Integer, ArrayList&lt; String &gt;&gt; hm = new HashMap();

        groupAnagrams( args, hm );
        System.out.println( hm );
    }


    public static void groupAnagrams( String[] list, HashMap&lt; Integer, ArrayList&lt; String &gt;&gt; hm ){

        for( int x=0; x&lt;list.length; x++ ){
            if( list[ x ] == null ) continue;

            String curX    = list[ x ];
            int    hashX   = primeHash( curX );

            hm.put( hashX, new ArrayList( Arrays.asList( curX )));

            for( int y=x+1; y&lt;list.length; y++ ){

                String curY    = list[ y ];
                int    hashY   = primeHash( curY );

                if( curY == null || curY.length() != curX.length())  continue;

                if( hashX == hashY ){
                    hm.get( hashX ).add( curY );

                    list[ y ] = null; // if its an anagram null it out to avoid checking again
                }
            }
        }
    }


// Utility Mehthods

    public static int primeHash( String word ){
        int productOfPrimes = 1;
        int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 
            37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

        for( char ch : word.toCharArray() ){
            productOfPrimes *= prime[ (int) ch - (int) 'a' ];
        }
        return productOfPrimes;
    }

}


Sample Input:


[ mother, mothre, dad, add, gift, gender ]



Output:


[ [mother, mothre], [dad,add], [gift], [gender] ]
Technical


   groupAnagrams( args );



That should be:

    groupAnagrams( args, hm );


Bug in copy/paste somehow?

1-liner statements, even simple ones like this:


      if( list[ x ] == null ) continue;



should be braced like:

       if( list[ x ] == null ) {
           continue;
       }


This prevents maintenance problems later, and makes revision history easier to follow.

Algorithm

Your algorithm is taking each member of the array, and comparing to each subsequent member, removing anagram matches.

The primeHash() method is interesting, but ultimately it is a red herring of sorts... and it only works for lower-case input words. You have obviously invested some thought in to it, but there's a simpler solution to that problem:

private static final String anagramKey(String word) {
    word = word.toLowerCase();
    char[] chars = word.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}


Take all letters, sort them, return a String. All anagrams of the same letters will have the same keys.

With that key system, the basic code can be come simpler with:

HashMap&lt;String,List&lt;String&gt;&gt; matchMap = new HashMap&lt;&gt;();
for (String word : args) {
    String key = anagramKey(word);
    if (!matchMap.containsKey(key)) {
        matchMap.put(key, new ArrayList&lt;String&gt;());
    }
    matchMap.get(key).add(word);
}

System.out.println(matchMap);


That reduces your problem to an \$O(n)\$ one.