Find sets of anagrams in a string array

Question

Below is a program where in which I find groupings of anagrams in a given string array. Is there a better way to do it?

public class FindAnagrams {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        String[] a = { "dear", "eard", "happy", "ppyah", "norway", "waynor", "anton", "notan", "ontan", "merry",
                "errymm", "yappah", "yapph" };

        int strLen = a.length;
        ArrayList<String> array1 = new ArrayList<String>();
        ArrayList<String> array2 = new ArrayList<String>();
        int subStrLen;
        HashMap<Character, Integer> hm1 = new HashMap<Character, Integer>();
        HashMap<String, HashMap<Character, Integer>> hm2 = new HashMap<String, HashMap<Character, Integer>>();

        for (int i = 0; i < strLen; i++) {
            // System.out.print(a[i]+" ");
            subStrLen = a[i].length();
            // System.out.println(subStrLen);
            char[] b = a[i].toCharArray();

            for (int j = 0; j < subStrLen; j++) {

                if (!hm1.containsKey(b[j])) {
                    hm1.put(b[j], 1);
                } else {
                    hm1.put(b[j], hm1.get(b[j]) + 1);
                }
            }

            hm2.put(a[i], (HashMap<Character, Integer>) hm1.clone());
            hm1.clear();
        }

        // System.out.println(hm2);

        for (Map.Entry<String, HashMap<Character, Integer>> entry1 : hm2.entrySet()) {
            String key1 = entry1.getKey();
            // HashMap<Character, Integer> valueE1 = entry1.getValue();

            for (Map.Entry<String, HashMap<Character, Integer>> entry2 : hm2.entrySet()) {

                // String key2 = entry2.getKey();
                HashMap<Character, Integer> valueE2 = entry2.getValue();

                if (hm2.get(key1).equals(valueE2)) {
                    array1.add(entry2.getKey());
                }

            }

            String x = array1.toString();

            if (array1.size() > 1 && !array2.contains(x)) {
                array2.add(x);
            }

            array1.clear();

        }

        System.out.println(array2);

    }

}

Answer 1

1. Your code looks complicated and opaque - names like a, array1 and hm1 are not at all helpful in making your code readable. Anyone submitting code to me with index variables called i and j would have the review immediately rejected. If you can't give variables good names, you don't really understand what you're doing, in my opinion.
2. There are easier ways of iterating over arrays etc. so you should use them.
3. Using contains() on an List is not an efficient operation. If you need to look up entries in a collection, consider using Maps or Sets.
4. Your encoding of the Strings is complex - dependent on the range of characters you wish to handle, an Array could be simpler and more efficient to work with than a Map. If you were happy to use the latin alphabet from 'a' - 'z' and be case-insensitive, each word could be encoded in a 26-element array of ints, or perhaps shorts (or even bytes if you were worried about space).

Here is your code reworked in line with most of those comments (but not the array approach):

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Anagrams {

  public static void main(String[] args) {
    String[] words = {"dear", "eard", "happy", "ppyah", "norway", "waynor", "anton", "notan", "ontan", "merry",
        "errymm", "yappah", "yapph"};

    Map<String, Map<Character, Integer>> wordToEncodedWord = new HashMap<>();

    // Encode words as Maps of letter counts
    for (String word : words) {
      Map<Character, Integer> encodedWord = new HashMap<>();
      for (char letter : word.toCharArray()) {
        int letterCount = encodedWord.getOrDefault(letter, 0);
        encodedWord.put(letter, letterCount + 1);
      }
      wordToEncodedWord.put(word, encodedWord);
    }

    Set<List<String>> allAnagramLists = new HashSet<>(); // As ArrayList isn't Comparable, can't easily use TreeSet :-(

    // Find words with the same encoding
    for (Map<Character, Integer> encodedWord : wordToEncodedWord.values()) {
      List<String> anagramList = new ArrayList<>();

      for (Map.Entry<String, Map<Character, Integer>> candidate : wordToEncodedWord.entrySet()) {
        Map<Character, Integer> candidateEncodedWord = candidate.getValue();
        String candidateWord = candidate.getKey();
        if (encodedWord.equals(candidateEncodedWord)) {
          anagramList.add(candidateWord);
        }
      }

      if ((anagramList.size() > 1) && !allAnagramLists.contains(anagramList)) {
        allAnagramLists.add(anagramList);
      }
    }

    System.out.println(allAnagramLists);
  }
}

It would be easier, I think, to simply "normalise" the words, by sorting the letters in them into alphabetical order and use a Map<String /*normalised word*/, List<String> /*words*/>. (The normalised word could also be defined as a char array).

So for example, your Map would have an entry with a Key of "ahppy", and the List value would contain "happy", "ppyah" and "yapph", and so on. Here is my solution based on that approach:

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

public class Anagrams2 {

  public static void main(String[] args) {
    String[] words = {"dear", "eard", "happy", "ppyah", "norway", "waynor", "anton", "notan", "ontan", "merry",
        "errymm", "yappah", "yapph"};

    Map<String, List<String>> allAnagramLists = new HashMap<>();

    for (String word : words) {
      char[] encodedWordChars = word.toCharArray();
      Arrays.sort(encodedWordChars);
      String encodedWord = new String(encodedWordChars);
      List<String> anagramList = allAnagramLists.getOrDefault(encodedWord, new ArrayList<String>());
      anagramList.add(word);
      allAnagramLists.put(encodedWord, anagramList);
    }

    for (List<String> anagramList : allAnagramLists.values()) {
      if (anagramList.size() > 1) {
        System.out.println(anagramList);
      }
    }
  }
}

I needed some practice with Java streams, so here's that solution expressed in stream form. Unfortunately, I can't see how to express the word normalisation operation as a lambda, as it doesn't fit a "one-liner".

import java.util.Arrays;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Anagrams3 {

  private static class Normaliser implements Function<String, String> {
    @Override
    public String apply(String word) {
      char[] wordChars = word.toCharArray();
      Arrays.sort(wordChars);
      return new String(wordChars);
    }
  }

  public static void main(String[] args) {
    String[] words = {"dear", "eard", "happy", "ppyah", "norway", "waynor", "anton", "notan", "ontan", "merry",
        "errymm", "yappah", "yapph"};
    Arrays.stream(words).//
        collect(Collectors.groupingBy(new Normaliser())). //
        forEach((key, anagramList) -> {
          if (anagramList.size() > 1)
            System.out.println(anagramList);
        });
  }
}