tech.guitarrapc.cóm

C#, PowerShell, Swift, Unity, Cloud, Serverless Technical Update and Features

Anagram check in C#

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

Anagram - Wikipedia

Let's see some article posted.

blog.agile.esm.co.jp

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

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

Let's try in C#.

Contents

Enumerable.Except

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 Docs

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!

gist.github.com

f:id:guitarrapc_tech:20161004034110p:plain

Same issue will happen with Enumerable.All.

https://msdn.microsoft.com/en-us/library/bb548541(v=vs.100).aspx

gist.github.com

f:id:guitarrapc_tech:20161004034209p:plain

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 Docs

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

gist.github.com

f:id:guitarrapc_tech:20161004040316p:plain

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

No LINQ

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

gist.github.com

f:id:guitarrapc_tech:20161004040246p:plain

O(n) : Dictionary

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

gist.github.com

f:id:guitarrapc_tech:20161004044404p:plain

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

gist.github.com

f:id:guitarrapc_tech:20161004044620p:plain

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

gist.github.com

f:id:guitarrapc_tech:20161004044747p:plain

Dictionary is much better performance than Sort algorithm.

Conclusion

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.