Group Anagrams

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

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

Explanation: There is no string in strs that can be rearranged to form "bat". The strings "nat" and "tan" are anagrams as they can be rearranged to form each other. The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Here are some other examples: strs = [""] Output: [[""]]

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

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

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        # Create a dictionary to store anagrams together.
        # The key will be the sorted string (representing the anagram group).
        # The value will be a list of strings that are anagrams of each other.
        anagram_groups = defaultdict(list)

        # Iterate through each string in the input list.
        for s in strs:
            # Sort the string to create a unique key for anagrams.
            # For example, "eat", "tea", and "ate" will all have the key "aet".
            sorted_string = "".join(sorted(s))

            # Append the original string to the list of anagrams for its corresponding key.
            anagram_groups[sorted_string].append(s)

        # Return the list of anagram groups (values of the dictionary).
        return list(anagram_groups.values())

Explanation:

The groupAnagrams function takes a list of strings strs as input and returns a list of lists, where each inner list contains strings that are anagrams of each other.

1. Initialization:

   • A defaultdict(list) called anagram_groups is created. This dictionary will store the anagrams. The keys of the dictionary will be the sorted versions of the strings, and the values will be lists of the original strings that are anagrams of each other.

2. Iterating through the input list:

   • The code iterates through each string s in the input list strs.

3. Sorting the string:

   • For each string s, it is sorted alphabetically using sorted(s). The sorted string is then joined back into a single string using "".join(). This sorted string is used as the key to identify anagrams.

4. Grouping anagrams:

   • The original string s is appended to the list associated with the sorted string key in the anagram_groups dictionary. This ensures that all anagrams are grouped together under the same key.

5. Returning the result:

   • Finally, the function returns a list of the values in the anagram_groups dictionary. Each value is a list of strings that are anagrams of each other.

Examples:

• Example 1:

  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
  result = groupAnagrams(strs)
  print(result)  # Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
  

• Example 2:

  strs = [""]
  result = groupAnagrams(strs)
  print(result)  # Output: [['']]
  

• Example 3:

  strs = ["a"]
  result = groupAnagrams(strs)
  print(result)  # Output: [['a']]
  

Time Complexity:

The time complexity of this function is O(N * K log K), where N is the number of strings in the input list and K is the average length of the strings. This is because we iterate through each string in the input list (O(N)), and for each string, we sort it (O(K log K)).

Space Complexity:

The space complexity of this function is O(N * K), where N is the number of strings in the input list and K is the average length of the strings. This is because we store the anagram groups in a dictionary, and in the worst case, each string could be in its own anagram group, requiring us to store all the strings in the dictionary.