Group Anagrams

Group Anagrams

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the orginal letters exactly once.

Example

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Approach 1:

When I first looked at this question, I thought it would be important to think about all the edge cases:

• what happens when list strs is empty
• what happens if the word in the list is empty
• what happens if some characters are not lowercase?

Luckily, all the edge cases that I could think of were explained by the constraints section:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters

Thanks to the last constraint, I thought I could

1. Simply sort each words in the list
2. Convert the list into a tuple to use as a key in hashmap
3. Return the list of values of hashmap with the same key

Implementation:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        h = collections.defaultdict(list)
        for word in strs:
            h[tuple(sorted(word))].append(word)
        return h.values()
        
        

Complexity Analysis:

Given that the length of list strs is N and the length of the longest word in strs is k,

Time Complexity: O(N * klogk)

Space Complexity: O(Nk)

Approach 2:

While creating a hashmap to group anagrams is okay, I thought that I could implement something that does not need sorting.

I could create an array of length 26 to keep count of frequencies of each characters of each word in strs.

Implementation:

class Solution:


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        h = collections.defaultdict(list)
        for word in strs:
            count = [0] * 26
            for char in word:
                count[ord(char) - ord('a')] += 1
            h[tuple(count)].append(word)
        return h.values()
        

Complexity Analysis:

Given that the length of list strs is N and the length of the longest word in strs is k,

Time Complexity: O(Nk)

Space Complexity: O(Nk)

Reflection

I think the key part of this question is thinking about what can be stored in a dictionary as key (immutable object) and value (mutable object).

While I knew I had to use ascii code, I could not think of this implementation and manipulation. I think it was a great exercise!