Leetcode 49 - Group Anagrams

Table of contents

Problem

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"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Explanation/Approach

The problem can be approached by categorizing anagrams using a hash table. Anagrams have the same character counts, so sorting the characters in each string can serve as a key to group them.

Hash Table and Sorting Approach:

• Hash Table: Use a hash table (like a Python dictionary) to store lists of anagrams. Each key in the hash table is a sorted tuple of characters from a string, and the value is a list of strings that, when sorted, equal the key.
• Sorting Strings: For each string in strs, sort its characters to form the key.
• Grouping: Add the original string to the list in the hash table corresponding to its sorted key.
• Result: The values of the hash table represent the groups of anagrams.

Character Frequency as Key:

• Count Frequency: For each string, create a fixed-size array (or a tuple) of length 26 (for each letter in the alphabet) to count the frequency of each character.
• Using Tuple as Key: Convert this array into a tuple (which is hashable) and use it as a key in a hash table.
• Grouping Anagrams: Strings with the same character frequency will have the same key and hence will be grouped together in the hash table.
• Result: The values of the hash table are the groups of anagrams.

Solution: Hash Table and Sorting

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # A dictionary to hold the sorted tuple of characters as keys and corresponding anagrams as values
        anagrams = {}

        for s in strs:
            # Sort the characters of the string to form the key
            key = tuple(sorted(s))
            # Add the original string to the corresponding list in the hash table
            if key not in anagrams:
                anagrams[key] = []
            anagrams[key].append(s)

        # Return the grouped anagrams
        return list(anagrams.values())

Time and Memory Complexity

The time complexity is O(nklogk), where n is the number of strings in strs and k is the maximum length of a string. This is due to the sorting of each string. The space complexity is O(nk), to store the hash table and the output list of anagrams.

Explanation

This solution uses sorting and hashing to group anagrams. Each string is transformed into a sorted tuple of characters, which acts as a unique identifier for its group of anagrams. The strings are then added to the corresponding lists in the hash table. Finally, the values of the hash table, which are lists of anagrams, are returned.

Visual Representation:

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

Sorted keys and corresponding anagrams:
('a', 'e', 't'): ['eat', 'tea', 'ate']
('a', 'n', 't'): ['tan', 'nat']
('a', 'b', 't'): ['bat']

Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

The visualization shows how each string is transformed into a sorted tuple of characters and grouped together with its anagrams in the hash table. This method effectively organizes the strings into groups of anagrams.

Solution: Hash Table with Character Count

To group anagrams without sorting each string, we can use the frequency of each character as a key. This approach involves counting the frequency of each character in a string and using the character counts as a hashable key.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}

        for s in strs:
            # Counting the frequency of each character in the string
            count = [0] * 26  # 26 for each letter in the alphabet
            for char in s:
                count[ord(char) - ord('a')] += 1

            # Using the tuple of counts as a key
            key = tuple(count)
            if key not in anagrams:
                anagrams[key] = []
            anagrams[key].append(s)

        return list(anagrams.values())

Time and Memory Complexity

The time complexity is O(nk), where n is the number of strings in strs and k is the maximum length of a string. This is due to iterating over each character of each string to count frequencies. The space complexity is O(nk), for storing the hash table and the output list of anagrams.

Explanation

This solution uses a count of characters in each string to form a unique hashable key. Strings that are anagrams of each other will have the same character count and thus be grouped together under the same key in the hash table. This approach avoids sorting each string, which can be more efficient, especially for longer strings.

Visualization Process:

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

Character Count and Grouping:
- (1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0): ["eat", "tea", "ate"]
- (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0): ["tan", "nat"]
- (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0): ["bat"]

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

Each string is translated into a count of its characters, which is used to group the anagrams. This method effectively organizes the strings into groups of anagrams without the need for sorting each string.