String Manipulation: Group Anagrams

Question:

You are given a list of strings. Write a function to group the anagrams together. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase.

Implement the function group_anagrams(strs: List[str]) -> List[List[str]], where

• strs is a list of strings that contains only lowercase letters.
• The function should return a list of lists, where each inner list contains a group of anagrams.

Example:

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

Answer:

To solve this problem, we can use a hashtable (dictionary) where the keys are the sorted strings (anagrams) and the values are lists of strings that are anagrams of each other.

1. Create an empty dictionary anagram_dict.
2. For each string s in strs:
   • Sort the characters of s and assign the result to a variable sorted_s.
   • If sorted_s is already a key in anagram_dict, append s to the corresponding value list.
   • Otherwise, create a new key-value pair in anagram_dict where the key is sorted_s and the value list contains only s.
3. Return the values of anagram_dict, which gives the grouped anagram lists.

Here's the Python code:

from typing import List

def group_anagrams(strs: List[str]) -> List[List[str]]:
    anagram_dict = {}
    
    for s in strs:
        sorted_s = ''.join(sorted(s))
        if sorted_s in anagram_dict:
            anagram_dict[sorted_s].append(s)
        else:
            anagram_dict[sorted_s] = [s]
    
    return list(anagram_dict.values())

The time complexity of this solution is O(NMlogM), where N is the number of strings in strs and M is the maximum length of the strings. This is because for each string, we sort its characters in O(MlogM) time. The space complexity is O(NM) as we need to store the grouped anagrams.