Leetcode Solution 49: Group Anagrams

Problem Statement 

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

  Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Every time we hear about anagrams, we automatically think would relate to how to find two words are anagrams, where we can solve in O(N), easy. That would result in a brute force solution.

Another quick thought would be sort each word and keep a map to track it, however, sorting is also not free.

Now we think harder, how can we avoid the O(MlgM) sorting (M is the word length) as the map's lookup key? Now the question becomes how we can generate a unique value (ideally string) for the same set of characters regardless of its order?  This is similar to the MD5 or SHA1 or hash value of certain object. So we can keep an array of chars, count the chars and translate that array into a string. Note simply count the sum of the array won't work, e.g., "ac" and "bb" will result in the same value.

Solutions

Brute force, for every pair of string in the array, check if they are anagrams. 

Time Complexity:O(M*N^2), M is the word length, and N is the string array length
Space Complexity: O(N)

Sort each string as key

As described above,we sort each string and use it as the lookup key so we can group the anagrams.
Time Complexity: O(N*M*LgM), M is the word length, and N is the string array length
Space Complexity: O(N)

"Hash" each string as key

Kind similar to hashing, we covert each string as key by generating a unique value using linear algorithm instead of sorting NlgN algorithm. 

Time Complexity: O(N*M), M is the word length, and N is the string array length
Space Complexity: O(N)

References

• Leetcode solution