Group Anagrams medium

Problem Statement

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1

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

Example 2

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

Example 3

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

Steps

1. Create a dictionary: We'll use a dictionary to store anagrams. The keys will be the sorted version of each string (since anagrams have the same letters, just rearranged), and the values will be lists of strings that share that sorted key.

2. Iterate through the input list: For each string in the input list strs, we:

   • Sort the string alphabetically.
   • Use the sorted string as the key in our dictionary.
   • If the key already exists, append the original string to the list associated with that key.
   • If the key doesn't exist, create a new list with the original string as its only element.

3. Extract the values: Finally, we extract the values (the lists of anagrams) from the dictionary. This gives us the desired grouped anagrams.

Explanation

The core idea is to use the sorted version of each string as a unique identifier for its anagram group. Sorting the string allows us to easily identify anagrams because they will have the same sorted form. The dictionary provides an efficient way to group strings based on their sorted representations.

Code

from collections import defaultdict

def groupAnagrams(strs):
    """
    Groups anagrams together.

    Args:
        strs: A list of strings.

    Returns:
        A list of lists, where each inner list contains strings that are anagrams of each other.
    """
    anagram_dict = defaultdict(list)  # Use defaultdict to avoid KeyError exceptions

    for word in strs:
        sorted_word = "".join(sorted(word)) # Sort the string and convert it back to string.
        anagram_dict[sorted_word].append(word)

    return list(anagram_dict.values()) #Return the values (list of anagrams) from the dictionary

Complexity

• Time Complexity: O(M * N * log N), where N is the average length of strings and M is the number of strings. The sorting of each string takes O(N * log N) time, and we do this for M strings.

• Space Complexity: O(M * N) in the worst case. This is because in the worst-case scenario (all strings are anagrams), the dictionary could store all strings, resulting in a space proportional to the total number of characters in all strings. The space usage could be less if there are fewer anagram groups.