LeetCode: Group Anagrams C# LeetCode: Group Anagrams C#
Given an array of strings, group anagrams together.

Example:

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


Note:

All inputs will be in lowercase.
The order of your output does not matter.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StringQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/778/
    /// &lt;/summary&gt;
    [TestClass]
    public class GroupAnagramsTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            string[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
            var result = GroupAnagramsClass.GroupAnagrams(strs);
            List&lt;IList&lt;string&gt;&gt; expected = new List&lt;IList&lt;string&gt;&gt;();
            expected.Add( new List&lt;string&gt; {"eat", "tea", "ate"});
            expected.Add( new List&lt;string&gt; {"tan", "nat"});
            expected.Add( new List&lt;string&gt; {"bat"});
            for (int i = 0; i &lt; result.Count; i++)
            {
                CollectionAssert.AreEqual(expected[i].ToList(), result[i].ToList());
            }
        }
    }

    public class GroupAnagramsClass
    {
        public static IList&lt;IList&lt;string&gt;&gt; GroupAnagrams(string[] strs)
        {
            Dictionary&lt;char[], List&lt;string&gt;&gt; dict = new Dictionary&lt;char[], List&lt;string&gt;&gt;(new CharComparer());
            foreach (var str in strs)
            {
                var key = str.ToCharArray();
                Array.Sort(key);
                if (!dict.TryGetValue(key, out var temp))
                {
                    temp = dict[key] = new List&lt;string&gt;();
                }
                temp.Add(str);
            }

            List&lt;IList&lt;string&gt;&gt; res = new List&lt;IList&lt;string&gt;&gt;(dict.Values.ToList());
            return res;
        }
    }

    public class CharComparer : IEqualityComparer&lt;char[]&gt;
    {
        public bool Equals(char[] x, char[] y)
        {
            if (x == null || y == null)
            {
                return false;
            }

            if (x.Length != y.Length)
            {
                return false;
            }

            for (int i = 0; i &lt; x.Length; i++)
            {
                if (x[i] != y[i])
                {
                    return false;
                }
            }

            return true;
        }

        public int GetHashCode(char[] obj)
        {
            return 0;
        }
    }
}


Please review for performance. I don't like me copying the dictionary into IList&lt;IList&lt;string&gt;. Is there a better way to do so, considering this the desired API defined by the question?
Deriving from IEqualityComparer versus EqualityComparer.

The MSDN docs say the following:


  We recommend that you derive from the EqualityComparer class instead of implementing the IEqualityComparer interface, because the EqualityComparer class tests for equality using the IEquatable.Equals method instead of the Object.Equals method. This is consistent with the Contains, IndexOf, LastIndexOf, and Remove methods of the Dictionary class and other generic collections.
  MSDN docs: IEqualityComparer


Dictionary versus Lookup

For grouping together objects from a sequence, where there might be a varying amount of items in each group, a Lookup is better than a Dictionary:

 var lookup = strs.ToLookup(key =&gt;
 {
     var array = key.ToCharArray();
     Array.Sort(array);
     return array;
 }, new CharComparer());
 return lookup.Select(grouping =&gt; (IList&lt;string&gt;)grouping.ToList()).ToList();


Comparing char-arrays

Since we're using Linq, let's use Linq:

public override bool Equals(char[] x, char[] y)
{
    if (x == null || y == null)
    {
        return false;
    }

    if (x.Length != y.Length)
    {
        return false;
    }

    return x.SequenceEqual(y);
}


The null behaviour is different and the length shortcut may stay, but the last loop we can offload to Linq.

Hashcode

Both Dictionary and Lookup rely on the hashcode returned by the equalitycomparer to categorise the keys into bins. These bins is what allows these collections to get times in \$O(1)\$. Always returning the same value is going to cause problems when your inputs get bigger. It will effectively turn the collections into single arrays which have to be looped over to get to the correct key. 

Creating good hashcodes is hard though, and I don't really know a good rule of thumb for creating them.

char[] versus string

All in all, the hashcode and equalitycomparer is such a headache, it's probably easier, and more readable to convert the sorted char[] back into a string, and use that as the key for the lookup:

 var lookup = strs.ToLookup(key =&gt;
 {
     var array = key.ToCharArray();
     Array.Sort(array);
     return new string(array);
 });
 return lookup.Select(grouping =&gt; (IList&lt;string&gt;)grouping.ToList()).ToList();