0049. Group Anagrams

Problem Category:: Array, Dictionary Neetcode Category:: Arrays and Hashing

https://leetcode.com/problems/group-anagrams/

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

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

Optimal

Dictionary of frequencies

Strings are anagrams only if their character counts are equal

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dictionary = {}
 
        for word in strs:
            charcounts = [0] * 26
            for char in word:
                charcounts[ord(char) - ord('a')] += 1
            
            tup_charcounts = tuple(charcounts)
 
            if tup_charcounts not in dictionary:
                dictionary[tuple(charcounts)] = [word]
            else:
                dictionary[tuple(charcounts)].append(word)
        
        return list(dictionary.values())

• Time complexity: The outer loop is $O(N)$, the inner loop we loop through the characters and do constant average operations with dictionaries so $O(NK)$ average
  • $k$ is the length of the longest ring in the list
• Space complexity: $O(NK)$ - size of dictionary

Others

Dictionary + sorting

Strings are anagrams only if their list of sorted characters are identical

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dictionary = {}
 
        for i in range(0, len(strs)):
            sorted_string_tup = tuple(sorted(strs[i])) # lists not hashable
            
            if sorted_string_tup not in dictionary:
                dictionary[sorted_string_tup] = [strs[i]]
            else:
                dictionary[sorted_string_tup].append(strs[i])
        
        return list(dictionary.values())

Time complexity

• Sort N strings of max length K → O(KlogK)
• For each string, we add to dictionary in constant time - overall O(NKlogK) Space complexity
• Up to N different string combinations (keys), each key is a tuple up to K length, so O(NK)
• The values themselves are the words, so $O(NK)$ overall

---

• task Format descriptive text, complete