49. Group Anagrams

Problem Statement in English

You’re given an array of strings strs. Group the anagrams together. You can return the answer in any order.

Approach

If 2 strings are anagrams, then they will have the same sorted string. So we can sort each string’s characters, rejoin them, and use it as a key in a hashmap to group the anagrams together.

And we’re done!

Solution in Python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        l = [sorted(s) for s in strs]

        hm = {}

        for i in range(len(l)):
            joined = "".join(l[i])
            if joined in hm:
                hm[joined].append(strs[i])
            else:
                hm[joined] = [strs[i]]

        return list(hm.values())

Complexity

• Time: $O(n \cdot m \cdot \log m)$
  where $n$ is the number of strings and $m$ is the average length of the strings. This is because we sort each string, which takes $O(m \cdot \log m)$ time, and we do this for all $n$ strings.

• Space: $O(n \cdot m)$
  where $n$ is the number of strings and $m$ is the average length of the strings. Since we store the sorted strings in a hashmap, which takes $O(n \cdot m)$ space in the worst case.

And we are done.