Solution: Group Anagrams

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

Solution #1: Using sorting and hashing

Press + to interact
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(k ...

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.