49. Group Anagrams

49. Group Anagrams

Summary

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example: Input: strs = ["eat","tea","tan","ate","nat","bat"]

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

Approach

Use a hash map where:

• the key is a 26-length tuple of character counts
• the value is the list of words with that character pattern

Anagrams always have exactly the same character counts, so they produce the same key.

Function

Initialization:

• hashmap = {}

For each word in strs:

1. Create a count array of length 26 filled with 0
2. For each character c in word, increment count[ord(c) - ord("a")]
3. Convert count to a tuple so it can be used as a hash-map key
4. If the key is not in hashmap, create a new list
5. Append word to hashmap[key]

Finally, return all values in the hash map.

Example 1: Input: strs = ["eat","tea","tan","ate","nat","bat"]

• "eat" -> (1, 0, 0, 0, 1, ..., 1 at t, ..., 0)
• "tea" -> same key as "eat"
• "ate" -> same key as "eat"
• "tan" -> (1, 0, 0, ..., 1 at n, ..., 1 at t, ..., 0)
• "nat" -> same key as "tan"
• "bat" -> its own key

So the groups are:

[["eat","tea","ate"], ["tan","nat"], ["bat"]]

Example 2: Input: strs = [""]

• "" -> (0, 0, ..., 0)

Output: [[""]]

Complexity

Time complexity: O(NW), where N is the number of words and W is the average word length. Building the 26-length tuple is O(26), which is constant.

Space complexity: O(NW) for storing the grouped words in the hash map.