Saturday, January 18, 2014

Reverse a c-style string

For example if a user enters a string “kodeknight” then on reversing the string will be “thginkedok“.

The basic approach here is to swap the first half of the string, with the next half.

Method 1 -  Iterative using string length
#include<stdio.h>
 
int string_length(char*);
void reverse(char*);
 
int main()
{
   char string[100];
 
   printf("Enter a string\n");
   gets(string);
 
   reverse(string);
 
   printf("Reverse of entered string is \"%s\".\n", string);
 
   return 0;
}
 
void reverse(char *string)
{
   int length, i;
   char *begin, *end, temp;
 
   length = string_length(string);
 
   begin = string;
   end = string;
 
   for ( i = 0 ; i < ( length - 1 ) ; i++ )
      end++;
// swap the chars till half of the length of the string
//begin with the end char and so on
   for ( i = 0 ; i < length/2 ; i++ )
   {
      temp = *end;
      *end = *begin;
      *begin = temp;
 
      begin++;
      end--;
   }
}
 
int string_length(char *ptr)
{
   int len = 0;
 
   while( *(ptr+len) != '\0' )
      len++;
 
   return len;
}

Note that instead of using temp variable, temp, we can use method to swap 2 variables without using extra variable, using ^ operator, the code will become:
int begin=0;
int end=str.length-1;

while(begin<end){
    str[begin]= (char) (str[begin]^str[end]);
    str[end]= (char)   (str[begin]^str[end]);
    str[begin]= (char) (str[end]^str[begin]);

    begin++;
    end--;       
}

Method 2 : Using recursion
void reverse(char *x, int beg, int end)
{
   char c;
 
   if (beg >= end)
      return;
 
   c = *(x+beg);
   *(x+beg) = *(x+end);
   *(x+end)   = c;
 
   reverse(x, ++begin, --end);
}
Time complexity - O(n) in both cases. Preferred solution here is iterative one. In recursion method we swap characters at the begin and at the end and then move towards the middle of the string. This method is inefficient due to repeated function calls and extra space used due to recursion.

0 comments:

Post a Comment