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

Solution: Group Anagrams

Explore solutions for grouping anagrams by using sorting and hashing techniques. Understand the time complexities involved and the limitations of brute force approaches, helping you develop efficient algorithmic strategies for this sorting and searching 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 ...