Printing mutual anagrams

Question

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:

1. 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.
2. 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<char[]> group = new ArrayList<char[]>();
    ArrayList<ArrayList<String>> originalList = new ArrayList<ArrayList<String>>();
    String[] tempstr = str.clone(); //clone could do deep copy, and avoid to change str.

    //Category group for str.
    outerloop:
    for(int pos=0; pos<tempstr.length; pos++){
        tempstr[pos]= tempstr[pos].trim().replaceAll(" ", "");
        char[] c = new char[tempstr[pos].length()];
        tempstr[pos].getChars(0,tempstr[pos].length(),c,0); //last character is at index srcEnd-1 
        Arrays.sort(c);//ignore character's order in string.
        ArrayList<String> sArrList = new ArrayList<String>();

        Iterator<char[]> 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 = originalList.get(group.indexOf(comparedChars));
                sArrList.add(str[pos]);
                continue outerloop;
            }
        }
        // can not find group
        sArrList.add(str[pos]);
        originalList.add(sArrList);
        group.add(c);
    }

    //Following begin to do sorting.
    String[] groupStr = new String[group.size()];
    Iterator<ArrayList<String>> it2 = originalList.iterator();
    for(int groupId=0 ; groupId<group.size() && it2.hasNext(); groupId++){
        ArrayList<String> temp = it2.next();
        Collections.sort(temp); // let string in each single row sort by alphabet.
        for(Iterator it3 = temp.iterator();it3.hasNext();){
            String ss = (String) it3.next();
            if(groupStr[groupId]==null || groupStr[groupId].length()==0) groupStr[groupId] = ss;
            else groupStr[groupId] += "," + ss;
        }
    }

Answer 1

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<String> 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<BigInteger, List<String>> result = new HashMap<BigInteger, List<String>>();

    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<String>();
            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;
}

Answer 2

[Work in progress]

Nice question. I assume you come from a C background? That it what your code looks like.

My main feedback would be to use Java's own classes and methods instead of implementing your own.

Don't do too much String operations

Your code does a trim() and a replaceAll(), in effect iterating the String twice, before you even do something useful with it. Also, you only check for whitespace. A safer way would be to filter the characters you need.

Naming

You have a lot of variables, some with the type in their name. Too many variables (with long, difficult names) make your code confusing. Give then names that denote their function not their type

Control structures and escape labels

While they might be useful, it is almost always a sign of something that coul be implemented simpler. Java provides you with very nice enhanced for loops, which make code easier to read. Easier to read code makes it easier to see optimisations as well.

My solution is:

private static void printAnagrams(List<String> 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<List<Character>, List<String>> result  = new HashMap<List<Character>, List<String>>();

    for (String s : input)
    {

        //First, create a sortedString
        List<Character> allLetters = new ArrayList<Character>();
        for (char ch : s.toCharArray())
        {
            if (Character.isLetter(ch))
            {
                allLetters.add(ch);
            }
        }
        Collections.sort(allLetters);



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

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

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

Answer 3

Thanks @RobAu to provide solutions, but there is a requirement that the head words should be sorted as well.

We need a custom class for TreeMap

class PrimeKey implements Comparable<PrimeKey> {
    BigInteger primeHash;
    String keyword;
    PrimeKey(BigInteger primeHash, String keyword) {
        this.primeHash = primeHash;
        this.keyword = keyword;
    }

    @Override
    public int compareTo(PrimeKey primeKey) {
        return this.keyword.compareTo(primeKey.keyword);
    }
}

Then reuse PrimeHash solution with additional steps that adding result into TreeMap for sorting

    private static void printAnagrams(List<String> 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<BigInteger, List<String>> 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<String>();
                anagrams.add(s);
                result.put(primeHash, anagrams);
            }
        }

        // sort each anagram-list
        result.values().forEach(Collections::sort);
        Map<PrimeKey, List<String>> sortedResult = new TreeMap<>();

        for (BigInteger key : result.keySet()) {
            List<String> strings = result.get(key);
            sortedResult.put(new PrimeKey(key, strings.get(0)), strings);
        }

        // and print
        sortedResult.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;
    }