Grouping of Anagrams
Objective: Given an array of strings, write an algorithm to group the anagrams.
Input: [rat, art, cat, act, dog, god, tar, pat] Output: [rat, art, tar] [cat, act] [pat] [dog, god]
If two strings are an anagram, then characters count in both the string must match. So if we sort both the strings, strings will match, we will use this property in our solution. Construct a map. Iterate through string array. For each string, sort the string and use it as key for a map and the actual(unsorted) string will be the value. Now all the strings which are anagram to the earlier string will have the same key in the map. So we will keep an array list as the value in the map and this array list will have one group of anagrams. See the example below for more understanding.
Input: [rat, art, cat, act, dog, god, tar, pat] [rat, art, tar] [cat, act] [pat] [dog, god]
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.