May 17, 2010

Reverse string in c++

By Mohammed Abualrob Algorithms and Data Structures 0 Comments

Problem

A typical interview question is to describe an algorithm to reverse a string of characters.

Solution

We need one pass through the characters of the string to get the string length or use a built in function to get that. Once the length of the string is found then one for loop can be used to switch the first character with the last character and the second character with the one before the last character and so on until the string is reversed in place. The number of iterations needed is half the string length. If the string has odd number of characters then the character in the middle of the string is not going to be switched with any character and will stay in its place.

Reverse string code

Here is an example C++ code to do that

//Includes
#include <iostream>
using namespace std;

void main ()
{
  //Sample string
  char str[] = "Please Reverse Me";

  //Find length of string. 
  int len = 0;
  while (str[len] != '\\0') { len++; }

  //Switch the first character with the last character
  //and the second character with the one before the last character
  //and so on.
  for (int i = 0; i < len/2; i++)
  {
	  char c = str[i];
	  str[i] = str[len-i-1];
	  str[len-i-1] = c;
  }

  //Print reversed string
  cout << "Reversed String = " << str;
}

//Includes

#include <iostream>

using namespace std;

void main ()

{

//Sample string

char str[] = "Please Reverse Me";

//Find length of string.

int len = 0;

while (str[len] != '\\0') { len++; }

//Switch the first character with the last character

//and the second character with the one before the last character

//and so on.

for (int i = 0; i < len/2; i++)

{

char c = str[i];

str[i] = str[len-i-1];

str[len-i-1] = c;

}

//Print reversed string

cout << "Reversed String = " << str;

}

Reverse string using recursion solution

We can write a recursive reverse string function to reverse a string. The stopping condition occurs when the string is one character in length in such case we just return that string otherwise we return string concatenation constructed from the first character and the recursive reverse of the rest of the characters. For example Reverse(“ABCD”) = Reverse(“BCD”) + “A”

Reverse string recursive method

Here is a Java reverse string program to do that

public class Test
{
   public static void main(String[] args)
   {
      System.out.println(Reverse("ABCDEFGH"));
   }

   public static String Reverse(String str) 
   {
      //Stopping condition
      if ((str == null) || (str.length()  <= 1)) 
      {
         return str;
      }

      //Recall: Reverse("ABCD") = Reverse("BCD") + "A"
      return Reverse(str.substring(1)) + str.charAt(0);
   }
}

public class Test

{

public static void main(String[] args)

{

System.out.println(Reverse("ABCDEFGH"));

}

public static String Reverse(String str)

{

//Stopping condition

if ((str == null) || (str.length() <= 1))

{

return str;

}

//Recall: Reverse("ABCD") = Reverse("BCD") + "A"

return Reverse(str.substring(1)) + str.charAt(0);

}

Another solution

Another variation of the first solution is to use bitwise XOR operation instead of using a temporary variable when switching characters. Actually this is another interview question in which they ask how to swap two variables without using a temporary variable.

Code

Here is a demo code in C++

//Includes
#include <iostream>

using namespace std;

void main ()
{
  //Sample string
  char str[] = "Please Reverse Me";

  //Find length of string. 
  int len = 0;
  while (str[len] != '\\0') { len++; }

  //Switch the first character with the last character
  //and the second character with the one before the last character
  //and so on.
  for (int i = 0; i < len/2; i++)
  {
     str[i]       ^= str[len-i-1];
     str[len-i-1] ^= str[i];
     str[i]       ^= str[len-i-1];
  }

  //Print reversed string
  cout << "Reversed String = " << str;
}