String Reversal Patterns/Algorithms

String Reversal with Swap algorithm – trivial one and average performance and the overhead of copying twice one to char array and other to original as strings are immutable. Extra variable is used as temp unnecessarily

    static string ReverseStringWithTemp(string sourceString)

        {

            char[] inputStream = sourceString.ToCharArray();

            for (int i = 0, j = sourceString.Length –  1; i < j; i++, j–)

            {

                char temp = inputStream[i];

                inputStream[i] = inputStream[j];

                inputStream[j] = temp;

            }

            return new string(inputStream);

        }

String Reversal with Copy to Char Array – trivial one an average performance and the overhead of copying twice one to char array and other to original as strings are immutable, no use of temp variable so memory efficient normal reversal

        static string ReverseStringWithoutTemp(string sourceString)

        {

            char[] inputStream = sourceString.ToCharArray();

            for (int i = 0, j = sourceString.Length – 1; i < j; i++, j–)

            {

                inputStream[j] = sourceString[i];

                inputStream[i] = sourceString[j];

            }

            return new string(inputStream);

        }

String Reversal with Stack – uses FILO structure for string reversal. Performance is almost equal to the normal reversals. Note that two loops are being used

        static string ReverseStringWithStack(string sourceString)

        {

            Stack<char> reverseString = new Stack<char>();

            for(int i = 0; i < sourceString.Length;i++)

            {

                reverseString.Push(sourceString[i]);

            }

            string targetString = string.Empty;

            while (reverseString.Count > 0)

            {

                targetString += reverseString.Pop();

            }

 

            return targetString;

        }

String Reversal with Bitwise XORing and quick one too without extra memory usage

        static string ReverseStringWithBitWiseXOR(string sourceString)

        {

            char[] inputStream = sourceString.ToCharArray();

 

            for (int i = 0, j = sourceString.Length – 1; i < j; i++, j–)

            {

                inputStream[i] ^= inputStream[j];

                inputStream[j] ^= inputStream[i];

                inputStream[i] ^= inputStream[j];

            }

            return new string(inputStream);

        }

In c# x1 ^= x2 equals to x1 = x1 ^ x2 where ^ is the bitwise XOR.

Let’s say we want to switch 2 binary values x1 = 100 and x2 = 111 so that x1 = 111 and x2 = 100.

XOR (Exclusive OR) table
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
First operation: x1 = x1 XOR x2
x1: 1 0 0
x2: 1 1 1
New x1: 0 1 1
Second operation x2 = x2 XOR x1
x1: 0 1 1
x2: 1 1 1
New x2: 1 0 0
Third operation: x1 = x1 XOR x2
x1: 0 1 1
x2: 1 0 0
New x1: 1 1 1

We now have x1 = 111 and x2 = 100.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s