There are no chance of me to write Anagram check in C#.
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 end
Let's try in C#.
Contents
- Contents
- Enumerable.Except
- O(n log n) : Sort with Enumerable.SequenceEqual
- O(n) : Dictionary
- Conclusion
Enumerable.Except
First, I thought it's not good to use Sort for performance issue, and imagine to use Enumerable.Except.
https://msdn.microsoft.com/en-us/library/bb300779(v=vs.100).aspx
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!
https://gist.github.com/guitarrapc/d730ab39b0a825a29ec18269db885e0b
Same issue will happen with Enumerable.All.
https://msdn.microsoft.com/en-us/library/bb548541(v=vs.100).aspx
https://gist.github.com/guitarrapc/fc8447f7a7f08892e6d53aac0b6385db
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.
It passes all tests. But is O(n log n)....
https://gist.github.com/guitarrapc/afd5e7db25aeb411adf7b9152d0bd804
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.
https://gist.github.com/guitarrapc/cc906c8b78f1442ba9ae679abe4af0b1
O(n) : Dictionary
Let's remove sort and just count with Dictionary. This bring much better performance, only 124ms.
https://gist.github.com/guitarrapc/44068234c146ba7023fc306e48c744dd
Also here's my friend @ichiohta's code.
https://gist.github.com/guitarrapc/21b97725c47e1eac3ef34a44da69467d
It takes much time in .GroupBy().ToDictionary(). Swap with my code brings 267ms -> 127ms.
https://gist.github.com/guitarrapc/eb10298d35b26a7b0ad36acace1795cb
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.
