Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Group Anagrams

Explore two methods for solving the group anagrams problem in Java. Understand how sorting combined with hashing can optimize the process and analyze their time complexities compared to brute force. Learn limitations of brute force, especially with duplicate characters, to gain deeper insight into algorithm design for string problems.

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 ...