Leetcode 49. Group Anagrams

Problem

Leetcode 49 - Group Anagrams

Example:

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

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

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

Approach

We can solve this problem by iterating through strs array then saving the count of the character then saving that into HashMap - since strs[i] consists of lowercase English letters, we can use [0]*26 as count array to reduce the cost

Visualization of the Approach:

strs = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
anagrams = {}

str = 'eat'
anagrams = {'aet' : ['eat'] }

str = 'tea'
anagrams = {'aet' : ['eat', 'tea']}

str = 'tan'
anagrams = {'aet' : ['eat', 'tea'], 'ant' : ['tan']}

str = 'ate'
anagrams = {'aet' : ['eat', 'tea', 'ate'], 'ant' : ['tan']}

str = 'nat'
anagrams = {'aet' : ['eat', 'tea', 'ate'], 'ant' : ['tan', 'nat']}

str = 'bat'
anagrams = {'aet' : ['eat', 'tea', 'ate'], 'ant' : ['tan', 'nat'], 'abt' : ['bat']}

result = [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Here is the Python code for the solution:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)

        for word in strs:
            count = [0] * 26
            for ch in word:
                count[ord(ch)-ord('a')] += 1
            
            anagrams[tuple(count)].append(word)
        
        return list(anagrams.values())

Time Complexity and Space Complexity

Time Complexity: $O(n*m)$ where $m$ is length of longest string $n$ is length of array

Space Complexity: $O(n)$