LeetCode #49: Group Anagrams

https://leetcode.com/problems/group-anagrams/

The brute force approach to solving this problem would be to compare each string with every other string in the given list to check if they are anagrams. However, this would take O(n^2) time complexity. A more efficient approach is to use a hash table to store the sorted version of each string, and group the strings based on their sorted version.

To solve this problem in Python 3, you can follow these steps:

1. Create an empty dictionary to store the sorted version of each string and their indices.
2. Iterate through the given list, and for each string, sort it and add it to the dictionary. If a sorted version of a string is already in the dictionary, we append the current string to its corresponding value.
3. Finally, return the values of the dictionary.

Python Code: Here’s the Python code to solve the Group Anagrams problem using the hash table approach:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Create an empty dictionary to store the sorted version of each string
        dict = {}
        
        # Iterate through the list
        for string in strs:
            # Sort the string and add it to the dictionary
            sorted_string = ''.join(sorted(string))
            if sorted_string in dict:
                # Append the current string to its corresponding value
                dict[sorted_string].append(string)
            else:
                dict[sorted_string] = [string]
        
        # Return the values of the dictionary
        return dict.values()

Runtime Complexity

The runtime complexity of the hash table approach is O(n k log k), where n is the number of strings in the given list and k is the length of the longest string in the list. This is because we are iterating through the given list, sorting each string (which takes O(k log k) time), and adding it to the dictionary.

Space Complexity

The space complexity of the solution is O(n k), as we are storing each string and its sorted version in a dictionary. In the worst-case scenario, every string in the given list is unique, so we need to store all n strings and their sorted versions in the dictionary. Additionally, the length of each string can be up to k, so the space required for each string is O(k).