GROUPANAGRAM - Editorial

editorial
, , , ,
1

Problem Link - Group Anagrams in Hashing

Problem:

Given an array of strings, group the anagrams together. Anagrams are strings that can be rearranged to form each other, like “eat”, “tea”, and “ate”.

Approach:

  • Sort and Use as Key: For each string in the input, sort the characters in lexicographical order. Since anagrams have the same characters in different orders, their sorted forms will be identical.

  • Group Using Hash Map: Use a hash map where the key is the sorted version of the string, and the value is a list of original strings (anagrams). If two strings are anagrams, they will have the same sorted key and will be grouped together in the same list.

  • Build Result: After processing all strings, the values of the map (lists of grouped anagrams) will be the final output.

Complexity:

  • Time Complexity: Sorting each string takes O(M log M), where M is the length of the string. Iterating over all N strings results in a time complexity of O(N * M log M).

  • Space Complexity: O(N) for storing the grouped anagrams in the hash map, where N is the total number of strings in the input.