Algorithms, C#

Finding if two Strings are Anagrams or not using XOR

In one of the previous post we saw how to find if two strings are Anagrams or not. The idea was to sort the characters of both the strings individually and then compare each character one by one.

The time complexity of the above algorithm depends on the Sorting Algorithm used to Sort the character arrays (which was O(NlogN) if we use Merge sort or Quick sort for example.)

There is another way to solve this problem using the bitwise operator XOR which basically returns 0 if all the characters are same in both the character sets.

Let us see how it works:

 

public static bool AreTwoStringsAnagramsUsingXor(string string1, string string2)
      {
          if (string.IsNullOrWhiteSpace(string1) || string.IsNullOrWhiteSpace(string2))
          {
              return false;
          }
         
          if (string1.Length != string2.Length)
          {
              return false;
          }
          
          char[] string1CharArray = string1.ToLower().ToCharArray();
          char[] string2CharArray = string2.ToLower().ToCharArray();
 
          int xor = 0;
 
          for (int i = 0; i < string1CharArray.Length; i++)
          {
              xor ^= string1CharArray[i] ^ string2CharArray[i];
          }
 
          if (xor == 0)
          {
              return true;    
          }
 
          return false;
 
      }

 

Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s