Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Group Anagrams

Here's a detailed analysis on how to solve the group anagrams problem

We'll cover the following...

Solution #1: Using sorting and hashing

Java
class Anagram {
 public static String groupAnagrams(String arr[]) {
  HashMap < String, List < String >> myMap = new HashMap < > ();
  for (int i = 0; i < arr.length; i++) // traverse all the words  
  {
   String word = arr[i];
   char[] letters = word.toCharArray(); // convert the given String Array's each index value to char array
   Arrays.sort(letters); // now sort all the words (based of letter's ASCII values using built in sort function for Arrays)  
   String newWord = new String(letters); //  and then re-convert each word to separate String
   if (myMap.containsKey(newWord)) // calculate hashcode of string after sorting  
    myMap.get(newWord).add(word);
   else {
    List < String > totalWords = new ArrayList < > ();
    totalWords.add(word); // Add words for the specific hashcode  
    myMap.put(newWord, totalWords);
   }
  }
  String anagrams = "";
  for (String s: myMap.keySet()) // print values if size is > 1, If you want to print non-anagrams, then print the values with size = 1  
  {
   List < String > values = myMap.get(s);
   if (values.size() > 1)
    anagrams = anagrams + values;
  }
  return anagrams;
 }
 public static void main(String[] args) {
  String arr[] = {
   "cat",
   "dog",
   "tac",
   "god",
   "act",
   "tom marvolo riddle ",
   "abc",
   "def",
   "cab",
   "fed",
   "clint eastwood ",
   "i am lord voldemort",
   "elvis",
   "old west action",
   "lives"
  };
  System.out.println(groupAnagrams(arr));
 }
}

First, this solution makes a copy of the array and sorts each string in the copy using the built-in sort() function of arrays. Then, it saves the sorted array into a HashMap called map. The key, in this case, is the sorted string, and the value is a vector of the indices of where it exists in the array. So, the hash table would have entries that look like:


                                          eilsv <-> {7, 9}
                                          abc <-> {1, 3}

Time complexity

Sorting one word takes O(klogk)O(klogk) ...