Be the first user to complete this post
|Add to List|
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]
- Maximum difference between two elements where larger element appears after the smaller element Medium