Printing mutual anagrams

Question:


An anagram is a word that can be written as a permutation of the
characters of another word, like "dirty room" and "dormitory"(ignore
spaces). However, "the" and "thee" are not anagrams, since "the" only
has a single "e" whereas "thee" has two "e" characters (spaces can
occur zero, or multiple times, however).


Give a list of words as input, you should output another list of
strings, each containing words that are mutual anagrams.


Each string of the output should be a single group of anagrams joined
with commas.


Within an output string, the expressions should be sorted
lexicographically. If a group contains only a single element, output
that one-element group as a single string. And the strings should also
be output in lexicographical order.


Given e.g.:

• pear

• amleth

• dormitory

• tinsel

• dirty room

• hamlet

• listen

• silent

The output would be:

amleth,hamlet
dirty room,dormitory
listen,silent,tinsel
pear

My solution is:

• Convert into each string to a char array, and in the meantime, compare to each char array group. After that, get how many groups for an input string array, and divide them into a respective group.

• Sort each group alphabetically, and eventually order by group.

Time-complexity is \$O(n^2)\$

I wrote code for this question, and it has a poor time-complexity. Are there any suggestions for this?

```
ArrayList group = new ArrayList();
ArrayList> originalList = new ArrayList>();
String[] tempstr = str.clone(); //clone could do deep copy, and avoid to change str.

//Category group for str.
outerloop:
for(int pos=0; pos sArrList = new ArrayList();

Iterator it = group.iterator();
while(it.hasNext()){
sArrList.clear();
char[] comparedChars = (char[])it.next();
if(Arrays.equals(comparedChars,c)){//only compare character in same index.
sArrList = original

A different way would be to use primeHashes (see https://stackoverflow.com/a/4237875/461499).

This prevents the need to sort.

private static void printAnagrams2(List input) {

    // our result structure.
    // key in the map is the sorted list of characters of the string
    // value is the list of anagrams found for this key
    Map> result = new HashMap>();

    for (String s : input) {
        BigInteger primeHash = calcPrimeHash(s);

        // Then add-or-create this in the resultmap
        if (result.containsKey(primeHash)) {
            result.get(primeHash).add(s);
        } else {
            List anagrams = new ArrayList();
            anagrams.add(s);
            result.put(primeHash, anagrams);
        }
    }

    // sort each anagram-list
    result.values().forEach(Collections::sort);

    // and print
    result.values().forEach(System.out::println);
}

private static int[] primes = {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};

private static BigInteger calcPrimeHash(String s) {
    BigInteger i = BigInteger.valueOf(1);
    for (char ch : s.toCharArray())
    {
        if (Character.isLetter(ch))
        {
            char c = Character.toLowerCase(ch);
            i = i.multiply(BigInteger.valueOf(primes[c - 'a']));
        }
    }
    return i;
}

StackExchange Code Review Q#153086, answer score: 7