Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Group Anagrams

Explore how to group anagrams by sorting strings and using a dictionary in C#. Learn to implement a solution that identifies anagram groups efficiently and analyze its time complexity for coding interviews.

We'll cover the following...

Solution: Using a dictionary and list

C# 9.0
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    /// <summary>
    /// Method to find anagram pairs.
    /// </summary>
    /// <param name="arr">An array of strings.</param>
    /// <returns>Group of anagrams.</returns>
    public static List<List<string>> Anagrams(string[] lst)
    {
        // Empty dictionary which holds subsets of all anagrams together
        Dictionary<string, List<string>> dictionary = new Dictionary<string, List<string>>();
        // traversing all the lst strings
        foreach (string str in lst)
        {
            char[] charArray = str.ToCharArray();
            // sorting the lst string and storing it in a key
            Array.Sort(charArray);
            string key = new string(charArray);
            // if the key is already in the dictionary then appending the original lst(Anagram).
            if (dictionary.ContainsKey(key))
            {
                dictionary[key].Add(str);
            }
            else // If there is no key in the dictionary
            {
                dictionary[key] = new List<string> { str };
            }
        }
        // traversing the whole dictionary and concatenating values and keys
        List<List<string>> result = new List<List<string>>();
        foreach (var pair in dictionary)
        {
            if (pair.Value.Count >= 2)
            {
                result.Add(pair.Value.OrderBy(x => x).ToList());
            }
        }
        result.Sort(CompareLists); // sort the arrays
        return result;
    }
    public static int CompareLists(List<string> list1, List<string> list2)
    {
        int minLength = Math.Min(list1.Count, list2.Count);
        for (int i = 0; i < minLength; i++)
        {
            int comparison = list1[i].CompareTo(list2[i]);
            if (comparison != 0)
            {
                return comparison;
            }
        }
        return list1.Count - list2.Count;
    }
    // Driver to test above code
    static void Main(string[] args)
    {
        string[] lst = new string[]
        {
            "tom marvolo riddle ",
            "abc",
            "def",
            "cab",
            "fed",
            "clint eastwood ",
            "i am lord voldemort",
            "elvis",
            "old west action",
            "lives"
        };
        List<List<string>> result = Anagrams(lst);
        var resultsToPrint = new List<string>();
        foreach (var anagram in result)
        {
            resultsToPrint.Add("[\"" + string.Join("\", \"", anagram) + "\"]");
        }
        Console.WriteLine("[" + string.Join(", ", resultsToPrint) + "]");
    }
}

Explanation

This solution sorts each input string in ascending order and considers it a key and the original string the value of the corresponding key. It then checks if the key exists in a dictionary. If it doesn’t exist, it means it is occurring for the very first time, so it maps an empty list to the key and appends a value to it. If the key is already present, it simply appends the value to the list.

Now, each list in the dictionary has anagrams. In the end, it iterates over the dictionary and stores all the values in a list if, in the key-value pair, the value corresponding to the key is greater than 2. The resultant list is returned, which has the pair of anagrams.

Time complexity

Sorting one word takes ...