IndexOutOfBoundsException While Checking and Printing Anagrams

Question

I've a set of inputs strings of the following type,

String[] arr = {"pear", "amleth", "dormitory", "tinsel", "dirty room", "hamlet", "listen", "silent"};

I need to write a program that checks which of these strings are anagrams and print them out in a comma separated list, lexicographically sorted. Thus expected output is

amleth, hamlet
dirty room, dormitory

.......

This is my code

public class Main {

    static void checkPrintAnagrams(String[] str){

        List<List<String>> out = new ArrayList<>();

        int[] check = new int[str.length];
        for(int i = 0; i < str.length; i++){
            List<String> list = new ArrayList<>();
            for(int j= 1; j < str.length; j++){
                if(check[j] != 1 && check[i] != 1){
                   if(isAnagram(str[i], str[j])){
                       list.add(str[i]);
                       list.add(str[j]);
                       check[j] = 1;
                       check[i] = 1;
                   }
                }
            }
            out.add(list);
        }

        Collections.sort(out, new Comparator<List<String>> () {
            @Override
            public int compare(List<String> a, List<String> b) {
                return a.get(1).compareTo(b.get(1));
            }
        });

        for(Iterator itr = out.iterator(); itr.hasNext();){
            List<String> l = (List<String>) itr.next();
            for(Iterator it = l.iterator(); it.hasNext();){
                System.out.print(it.next() + ",");
            }
            System.out.println();
        }
    }

    static boolean isAnagram(String firstWord, String secondWord) {
        char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
        char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
        Arrays.sort(word1);
        Arrays.sort(word2);
        return Arrays.equals(word1, word2);
    }


    public static void main(String[] args) {
    // write your code here
        String[] arr = {"pear", "amleth", "dormitory", "tinsel", "dirty room", "hamlet", "listen", "silent"};
        checkPrintAnagrams(arr);
    }
}

The sorting of a List of List part in this code is what I've picked up from the net without understanding completely and like anything not completely understood ends up with an out of bound exception.

This is my error message.

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
    at java.util.ArrayList.rangeCheck(ArrayList.java:653)
    at java.util.ArrayList.get(ArrayList.java:429)
    at io.soumasish.Main$1.compare(Main.java:31)
    at io.soumasish.Main$1.compare(Main.java:28)
    at java.util.TimSort.countRunAndMakeAscending(TimSort.java:355)
    at java.util.TimSort.sort(TimSort.java:220)
    at java.util.Arrays.sort(Arrays.java:1512)
    at java.util.ArrayList.sort(ArrayList.java:1454)
    at java.util.Collections.sort(Collections.java:175)
    at io.soumasish.Main.checkPrintAnagrams(Main.java:28)
    at io.soumasish.Main.main(Main.java:62)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:497)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)

Would appreciate help in understanding the Collections sort part and how to implement it correctly in this context.

Answer 1

You can use a Stream and groupingBy to create a Map<String, List<String>>.

All you need to do is to group the data by some normalised for:

• remove all spaces
• sort the characters alphabetically
• create a String

Simple:

Map<String, List<String>> anagrams = Stream.of(arr).collect(groupingBy(s -> {
    char[] chars = s.replaceAll("\\s", "").toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}));

For example:

anagrams.forEach((k, v) -> {
    System.out.printf("Anagrams of %s - %s%n", k, v);
});

Output:

Anagrams of eilnst - [tinsel, listen, silent]
Anagrams of dimoorrty - [dormitory, dirty room]
Anagrams of aehlmt - [amleth, hamlet]
Anagrams of aepr - [pear]

Answer 2

Put comments and print statements in your code if you don't understand it; that will help you understand it. Your problem in understanding that code is thus:

If you want to make all possible pairs out of an array, you can use two loops.

String[] arr = {"pear", "amleth", "dormitory", "tinsel", "dirty room", "hamlet", "listen", "silent"};

// Comment: first loop, the outer loop, iterates from 0 to length
for ( int i=0, il = arr.length; i<il; ++i ) {
    // Comment: second loop, the inner loop, iterates from 
    // the starting position of the first loop to length
    for( int j=i, jl=arr.length; j<jl; ++j ) {
        System.out.println("S1="+arr[i]+":S2="+arr[j]);
    }
}

You will see that your loops do not do this. Thus, you are not passing what you expect into the sort routine. You can determined this with debug statements. Print out what is in the out list before it gets to the sort routine.

Lastly, there are other issues with your algorithm, but if you carefully comment your code and put debug print statements throughout, you will get a better understanding of what's happening in the code.

Answer 3

Here's some guidance, not a total solution, since you're looking for some understanding.

First, the error trace shows you exactly what is wrong and where, it's just a little bit cryptic. The line

at io.soumasish.Main.checkPrintAnagrams(Main.java:28)

is the last line in the call trace that was coded by you. Everything else from the top down to that line is in library code that you invoked. So the problem is in line 28 of your Main.java file. I'm going to guess that it's this line:

return a.get(1).compareTo(b.get(1));

So what's going on in this code? First, the variables a and b are of type List<String> per the signature of the compare() method. The get() method on List takes an integer argument and returns, in this case, a String. And the integer argument is an index into the List. Here's the key: the index is 0-relative, which means you are asking for the second element in the List. The exception that is thrown indicates that in at least one of a and b, there is no second element. It has either zero or one elements in it.

So what do I do about the Comparator?

Yeah, that's the question. So think about this: how would you sort two lists of things? I'm guessing that you'd want to do something like this:

• If both lists are empty, return 0 (equal)
• If only a is empty, return -1 (less than)
• If only b is empty, return 1 (greater than)
• If they both have elements, check the first element
• If the first elements are not the same, return the comparison of those
• If one list only has one element, return (-1 or 1 depending)
• Check the second element

and so forth. You can work that over into a proper algorithm, I'm sure.

Bottom line

You need to work on that Comparator so it correctly compares two objects of type List<String> that may have any number of elements.

I have implemented the compare() method below. I've tried to write it so that the underlying ideas are clear.

public int compare(List<String> a, List<String> b) {
    int aSize = a.size();
    int bSize = b.size();
    int index = 0;
    while (index < aSize && index < bSize) {
        String aStr = a.get(index);
        String bStr = b.get(index);
        int comp = aStr.compareTo(bStr);
        if (comp != 0)
            return comp;
        index++;
    }
    return aSize < bSize ? -1 : (aSize > bSize ? 1 : 0);
}

You may notice that there are still issues in your logic, but at least the exception is gone. :-)