49. 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 original letters exactly once.

Solution

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = defaultdict(list)
        for str in strs:
            freq = [0] * 26
            for c in str:
                freq[ord(c) - ord("a")] += 1
            ans[tuple(freq)].append(str)
        return ans.values()

Time Complexity: O(n)

Space Complexity: O(n)

Explanation

The idea is to form a frequency map for each of the words and have these serve as the keys in a dictionary. The key to doing this is to convert a frequency array to a tuple so that it become an immutable value (required by dictionary).