Reversing a string is a popular question in most campus hiring interviews. There could be several ways one can think of to do this. We will be looking at some of those.
In this article we will not look at the Reverse method provided by the .NET libraries; we will instead try to implement it by our own logic. However we will be using the ToCharArray method in most of our examples.
Let’s start with the most basic that uses two arrays, one to store the input and another for the output and uses two variables to traverse from the begining and end and assigns the values from the input array to the output array.
|
///Need one extra array for result, need to traverse full array.
public static stringReverseString1 (string str)
{
char[] chars = str.ToCharArray();
char[] result = newchar[chars.Length];
for (int i =0, j = str.Length - 1; i < str.Length; i++, j--)
{
result[i] = chars[j];
}
return new string(result);
} |
I am sure we can do much better here, so let’s do that. Now we will use the swapping for the same (as we used in the sorting algorithms) also if you look at, we are only traversing half of the array.
|
///Uses swap method to reverse; need to traverse only half of the array.
public static stringReverseString2(string str)
{
char[] chars = str.ToCharArray();
for (int i =0, j = str.Length - 1; i < j; i++, j--)
{
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
return new string(chars);
} |
Don’t want to use any temp variable, so this is for you, here we are using an in-pace swap.
|
///Here is the use of in-place swap without any temp variable
public static stringReverseString3 (string str)
{
char[] chars = str.ToCharArray();
for (int i = 0, j =str.Length - 1; i < j; i++, j--)
{
chars[i] = str[j];
chars[j] = str[i];
}
return new string(chars);
} |
Following is similar to above except its without copy to char array.
|
///String Reversal without Copy to Char Array it's i <= j as we need to getthe middle /// character in case of odd number of characters in the string
public static stringReverseString3b(string str)
{
char[] chars = new char[str.Length];
for (int i = 0, j =str.Length - 1; i <= j; i++, j--)
{
chars[i] = str[j];
chars[j] = str[i];
}
return new string(chars);
} |
Now let’s try something new, Stacks, we all know how stack works, in other words LIFO. So we will be using the same here.
|
///String reversal with stack [Please note here Stack_Array is my custom Stackclass, ///you can replace this with provided by .NET]
public static stringReverseString4(string str)
{
Stack_Array stk1 = newStack_Array(str.Length);
foreach (charc in str)
stk1.Push(c);
string revString = null;
foreach (charc in str)
revString += stk1.Pop();
return revString;
} |
Now for something very different, XOR; yes we will be using XOR to reverse the string. Want to know how it works? First try it out on pen and paper. I have also explained it in the comments however it’s better if you try it yourself first.
|
///String reversal with XOR (^); interesting way to reversal
/// A[i] = A[i] ^ A[len] -> A[i] = 80 ^ 73 -> A[i] = 25
/// A[len] = A[len] ^ A[i] -> A[len] = 73 ^ 25 -> A[len] = 80
/// A[i] = A[i] ^ A[len] -> A[i] = 25 ^ 80 -> A[i] = 73
public static stringReverseString5(string str)
{
char[] inputstream = str.ToCharArray();
int length = str.Length - 1;
for (int i =0; i < length; i++, length--)
{
inputstream[i] ^= inputstream[length];
inputstream[length] ^= inputstream[i];
inputstream[i] ^= inputstream[length];
}
return new string(inputstream);
} |
So much for iterative ways. Now to try recursion. The following is probability the shortest and simplest way to reverse a sting using recursion.
|
///Recursion method; simple and regular performance for small strings
public static stringReverseString_Rec(string str)
{
if (str.Length <= 1)
return str;
else
return ReverseString_Rec(str.Substring(1)) +str[0];
} |
Another variant using recursion is not so short but is simple though.
|
///Another way of recursion; need to index as 0
public static stringReverseString_Rec2(string str, int index)
{
char[] chars = str.ToCharArray();
int len = chars.Length;
if (index < len / 2)
{
char c = chars[index];
chars[index] = chars[len - index - 1];
chars[len - index - 1] = c;
index++;
return ReverseString_Rec2(new string (chars),index);
}
else
{
return new string(chars);
}
} |
Please let me know your comments/suggestions or if you have a better way. :)