0049.Group Anagrams

• Link: 49. Group Anagrams - Medium
• Track: NeetCode150

Question

Example 1:

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

Restate the problem

Anagram: same character, same frequency, different order

• Given a list of string, contain english lowercase letter
• Process: group the strings that are anagrams of each other
• Return: a list of groups

Edge Case

• Empty strs, return []
• ["a"], return [["a"]]
• ["", ""], return [["",""]]

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Hashmap	O($n\ast k$)	$O(n\ast k)$
Method 2	Sort (key = sorted word)	O($n\ast klogk$)	$O(n\ast k)$

Method 1 - Hashmap

Build a “signature” for each word, use it as the hash map key, and group words with the same signature.

Approach

• Create a hashmap: signature → list of words
• For each word:
  • Count frequency of 26 letters (counts[0..25])
  • Convert to tuple as signature
  • Append word to hashmap [signature]
• Return hashmap values

Complexity

• Time Complexity: O($n\ast k$)
  • n = number of words
  • k = average length of each word
• Space Complexity: O($n\ast k$)

Code

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = defaultdict(list)
        for word in strs:
            counts = [0] * 26 # list can not be key
            for char in word:
                counts[ord(char) - ord('a')] += 1
            
            # key_str = "".join(str(counts))
            key = tuple(counts)
            dic[key].append(word)
        
        res = []
        for key, val in dic.items():
            res.append(val)
        
        return res

Method 2 - Sort (key = sorted word)

Approach

Complexity

• Time Complexity: O($n\ast klogk$)
• Space Complexity: $O(n\ast k)$

Code

from collections import defaultdict
 
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for word in strs:
            key = ''.join(sorted(word))   # or tuple(sorted(word))
            groups[key].append(word)
        
        return [group for group in groups.values()] # list(groups.values())

---

Common mistake

• List can not be a hashmap key