Group Anagrams - Leetcode Solution

Problem Statement:

Given an array of strings, group anagrams together.

Example:

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

Solution:

To solve this problem, we can utilize the fact that two strings are anagrams if and only if they have the same set of characters. In other words, if we sort the characters in each string and group strings with the same sorted form together, we will obtain groups of anagrams.

Algorithm:

1. Create an empty dictionary to store groups of anagrams.
2. Iterate through each string in the input array: a. Sort the characters in the string. b. Use the sorted string as a key to store the original string in the dictionary.
3. Return the values of the dictionary as the grouped anagrams.

Code:

Here's the Python code that implements the above algorithm:

from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Create an empty dictionary to store groups of anagrams
        anagrams = {}
        
        # Iterate through each string in the input array
        for s in strs:
            # Sort the characters in the string
            sorted_s = "".join(sorted(s))
            
            # Use the sorted string as a key to store the original string in the dictionary
            if sorted_s not in anagrams:
                anagrams[sorted_s] = [s]
            else:
                anagrams[sorted_s].append(s)
        
        # Return the values of the dictionary as the grouped anagrams
        return list(anagrams.values())

Complexity Analysis:

• Time complexity: O(nklogk) where n is the number of strings and k is the maximum length of a string. The time complexity is dominated by the cost of sorting each string.
• Space complexity: O(nk) to store the dictionary and the output array.

1