Group Anagrams (Leetcode #49)

Question:

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.

Example 1:

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

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10<sup>4</sup>

• [0 <= strs[](https://leetcode.com/problems/group-anagrams/)i].length <= 100

• strs[i] consists of lowercase English letters.

Answer:

1. Create a hashmap to keep track of each word where the key is the sorted word and the values will be the original word

2. Return the values of the hashmap in a list form

word = {}
for w in strs:
    sorted_string = "".join(sorted(w))
    if sorted_string not in word:
        word[sorted_string] = []
    word[sorted_string].append(w)
return list(word.values())

Time complexity

Let's break this down into each part.

1. Loop each item in strs will cost you O(N)

2. Sorting string with average length K will cost you O(klogk)

3. Hence the overall time complexity will be O(n * k log k)

Space Complexity

1. When we sort the text we need a temporary space of O(k)

2. We need to store each sorted string in the hashmap

3. The overall space complexity will be O(n * k)