LeetCode Solutions Blog

Group Anagrams

Number: 49

Difficulty: Medium

Paid? No

Problem Description

Given an array of strings, group the anagrams together. Anagrams are words that can be formed by rearranging the letters of another word. The answer can be returned in any order.

Key Insights

Anagrams have the same characters when sorted alphabetically.
Sorting each string provides a unique key for grouping.
Use a hash table (dictionary) to map each sorted key to a list of its original strings.
Finally, gather all the lists from the dictionary to form the result.

Space and Time Complexity

Time Complexity: O(n * k log k), where n is the number of strings and k is the maximum length of a string (due to sorting each string). Space Complexity: O(n * k) for storing the grouped strings in the hash table.

Solution

The primary idea is to iterate through each string, sort it to obtain a key that represents its character composition, and then group the original string under this key in a hash table. After processing all strings, the values of the hash table will be the groups of anagrams. This approach efficiently groups anagrams by leveraging sorting and a dictionary for constant-time lookups.

Code Solutions

# Python solution for grouping anagrams
from collections import defaultdict

def groupAnagrams(strs):
    # Create a dictionary to hold lists of anagrams; default to an empty list for new keys
    anagrams = defaultdict(list)
    # Iterate over each string in the input list
    for s in strs:
        # Sort the string to use as a key; sorted returns a list so join back to string
        key = "".join(sorted(s))
        # Append the original string under the sorted key
        anagrams[key].append(s)
    # Return the grouped anagrams as a list of lists
    return list(anagrams.values())

# Example usage:
if __name__ == "__main__":
    strs = ["eat","tea","tan","ate","nat","bat"]
    result = groupAnagrams(strs)
    print(result)