We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Group Anagrams

Difficulty: Medium

Problem Description

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

Key Insights

  • Anagrams are words that can be formed by rearranging the letters of another word.
  • The core idea is to use a characteristic of anagrams for grouping, such as sorting the characters in each string or using a frequency count of characters.
  • A hash table (dictionary) is a suitable data structure to map the sorted string (or character count) to the list of anagrams.

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 (for sorting). Space Complexity: O(N * K) for storing the grouped anagrams in a hash table.

Solution

To solve the problem, we can utilize a hash table (dictionary) to group the anagrams. For each string in the input array, we can either sort the string or create a character frequency count. We use the sorted string (or the frequency tuple) as the key in the hash table, and append the original string to the list corresponding to that key. Finally, we return all the grouped anagrams from the hash table.

Code Solutions

def groupAnagrams(strs):
    anagrams = {}
    for s in strs:
        # Sort the string to form a key
        key = ''.join(sorted(s))
        # Add the original string to the corresponding anagram group
        if key in anagrams:
            anagrams[key].append(s)
        else:
            anagrams[key] = [s]
    # Return the values from the dictionary as a list of groups
    return list(anagrams.values())
← Back to All Questions