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 arrayArrays.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 Stringif (myMap.containsKey(newWord)) // calculate hashcode of string after sortingmyMap.get(newWord).add(word);else {List < String > totalWords = new ArrayList < > ();totalWords.add(word); // Add words for the specific hashcodemyMap.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 ...
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.