|
This post is completed by 1 user
|
Add to List |
384. Grouping of Anagrams
Objective: Given an array of strings, write an algorithm to group the anagrams.
Example:
Input: [rat, art, cat, act, dog, god, tar, pat] Output: [rat, art, tar] [cat, act] [pat] [dog, god]
Approach:
If two strings are an anagram, then the characters count in both strings must match. So if we sort both the strings, the 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 a key for a map and the actual(unsorted) string will be the value. Now all the strings that 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.
Output:
Input: [rat, art, cat, act, dog, god, tar, pat] [rat, art, tar] [cat, act] [pat] [dog, god]