LeetCode 049 - Group Anagrams

2026-04-05

medium　array

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: strs = ["act","pots","tops","cat","stop","hat"]

Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Example 2:

Input: strs = ["x"]

Output: [["x"]]

Example 3:

Input: strs = [""]

Output: [[""]]

Constraints:

1 <= strs.length <= 1000.0 <= strs[i].length <= 100strs[i] is made up of lowercase English letters.

• 1 <= strs.length <= 1000.
• 0 <= strs[i].length <= 100
• strs[i] is made up of lowercase English letters.

Solution 1:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Solve this problem with a brute-force approach using sorting
        # We use 'compared_str' to keep track of already processed anagram patterns to avoid duplicate groups.
        
        # First, we iterate through the list. For each word, we sort its characters to create a standard "pattern".
        # Second, we check if this pattern has already been processed. If yes, we skip to the next word.
        # Third, we use an inner loop to check all words in the list. If a word's sorted pattern matches our current pattern, we add the ORIGINAL word to our current group.
        # Finally, we record the pattern in 'compared_str' as processed, and append the current group to the final result.
        
        # Time complexity is O(n^2 * m log m), where n is the length of 'strs' and m is the max length of a string.
        # (We have nested loops O(n^2), and inside the inner loop we sort the string O(m log m)).
        # Space complexity is O(n * m) to store the result list and the 'compared_str' list.

        result_list = []
        compared_str = []
        for str in strs:
            current_result_list = []
            str = sorted(str)
            if str in compared_str:
                continue
            for compare_str in strs:
                sorted_str = sorted(compare_str).copy()
                if str == sorted_str:
                    current_result_list.append(compare_str)
            compared_str.append(str)
            result_list.append(current_result_list)
        return result_list

Solution 2:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Optimal Solution using Hash Map
        # We use a hash map (str_hash_map) to group anagrams together. 
        # The key is the sorted version of the string, and the value is a list of the original strings.
        
        # Time Complexity: O(n * m log m), where 'n' is the total number of strings in 'strs', 
        # and 'm' is the maximum length of a string. Sorting each string takes O(m log m) time.
        # Space Complexity: O(n * m), as we store all 'n' strings of maximum length 'm' inside the hash map.
        str_hash_map = {}
        for str in strs:
            sorted_str = "".join(sorted(str))
            if sorted_str in str_hash_map:
                str_hash_map[sorted_str].append(str)
            else:
                str_hash_map[sorted_str] = [str]
        return list(str_hash_map.values())

Solution 3:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Optimal Solution using Character Count (Frequency Array)
        # Instead of sorting, we use an array of size 26 to count the frequency of each letter.
        # This reduces the time complexity from O(n * m log m) to O(n * m).
        
        # Time Complexity: O(n * m), where 'n' is the number of strings and 'm' is the max string length.
        # Space Complexity: O(n * m), as we store all 'n' strings of maximum length 'm' inside the hash map.
        str_hash_map = {}
        for str in strs:
            char_list = [0] * 26
            for char in str:
                char_list[ord(char) - ord('a')] += 1
            if tuple(char_list) in str_hash_map:
                str_hash_map[tuple(char_list)].append(str)
            else:
                str_hash_map[tuple(char_list)] = [str]
        return list(str_hash_map.values())