Technical updates

Anagram check in C#

There are no chance of me to write Anagram check in C#.

Anagram - Wikipedia

Let's see some article posted.

It says he met anagram question with code interview and answer was as follows.

def anagram(s1, s2)
  s1.chars.sort == s2.chars.sort

Let's try in C#.



First, I thought it's not good to use Sort for performance issue, and imagine to use Enumerable.Except.

Enumerable.Except Method (System.Linq) | Microsoft Learn

But soon I forgive it. Except will be worth when duplicate character is accepted but may take too much check if no allowed. You can see #7 failed with "aba == bab" was true!

Same issue will happen with Enumerable.All.

O(n log n) : Sort with Enumerable.SequenceEqual

May be one of the easiest way is sort array then check. Let's use Enumerable.SequenceEqual() to sorted array.

Enumerable.SequenceEqual Method (System.Linq) | Microsoft Learn

It passes all tests. But is O(n log n)....

string null conditional check ?. will cause duplicate null check, so it may take bit more time.


I like LINQ but let's try no LINQ. Looks like better performance, 181ms.

O(n) : Dictionary

Let's remove sort and just count with Dictionary. This bring much better performance, only 124ms.

Also here's my friend @ichiohta's code.

It takes much time in .GroupBy().ToDictionary(). Swap with my code brings 267ms -> 127ms.

Dictionary is much better performance than Sort algorithm.


Pattern Algorithm time in 12 test x 100000
Sort (LINQ : Enumerable.SequenceEqual) O(n log n) 280ms
Sort (LINQ : Enumerable.SequenceEqual + ?.) O(n log n) 290ms - 580ms
Sort (NO LINQ) O(n log n) 181ms
Dictionary (NO LINQ) O(n) 124ms
Dictionary (LINQ : GroupBy().ToDictionary()) O(n) 267ms

What's the most readable and fast enough code for you? More idea is much appreciated.