Group Anagrams medium

Problem Statement

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

Steps

1. Create a Dictionary: Use a dictionary to store anagrams. The key will be a sorted string representation of each word (since anagrams have the same letters, just rearranged), and the value will be a list of strings that are anagrams of that key.

2. Iterate Through Strings: Iterate through each string in the input array strs.

3. Sort and Use as Key: For each string, sort its characters alphabetically. This sorted string becomes the key in our dictionary.

4. Add to Dictionary: If the sorted string (key) already exists in the dictionary, add the original unsorted string to its corresponding list (value). Otherwise, create a new entry in the dictionary with the sorted string as the key and a new list containing the original string as the value.

5. Return Values: Finally, return a list containing all the lists of anagrams (the values from the dictionary).

Explanation

The core idea is to use the sorted representation of each word as a unique identifier for its anagram group. Sorting ensures that different arrangements of the same letters will produce the same key. The dictionary efficiently groups anagrams based on this sorted key.

Code (C#)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        Dictionary<string, List<string>> anagramGroups = new Dictionary<string, List<string>>();

        foreach (string str in strs) {
            char[] charArray = str.ToCharArray();
            Array.Sort(charArray);
            string sortedStr = new string(charArray);

            if (anagramGroups.ContainsKey(sortedStr)) {
                anagramGroups[sortedStr].Add(str);
            } else {
                anagramGroups[sortedStr] = new List<string>() { str };
            }
        }

        return anagramGroups.Values.ToList();
    }
}

Complexity

• Time Complexity: O(M * N * log N), where N is the average length of strings and M is the number of strings. The dominant factor is sorting each string (O(N * log N) per string), which we do M times.

• Space Complexity: O(M * N) in the worst case. This happens when all strings are anagrams of each other, resulting in one large list in the dictionary. In the best case (no anagrams), it's O(M). The space is primarily used to store the dictionary and its lists.