Friday, 1 April 2011

String Reverse

 

Question:

    Implement strrev is a possible interview question. How would you do it ?

The simple way is to go to the back of the string, allocate a buffer and push the character from the right to left into the buffer and return it.

But the above approach use extra space

Code:

char* str_rev(char* str)
{
    char* istr = str;
    char* output= (char*) malloc(strlen(str));
    char* ioutput = output;
    while(*str != '\0') {
        str++;
    }
 
    while(--str != istr) {
        *output = *str;
        output++;
    }
    *output = *str;
    *(output+1) = '\0';
    return ioutput;
}
 
void main()
{
    char* rstr = str_rev("rajan");
 
}

 

How would you do without using this extra space?

Just swap the last element in the string with the first element until you reach the middle.

char* str_rev(char* str)
{
    char* tstr = str;
    char* istr = tstr; // string start
    while(*tstr != '\0') tstr++;
    char* estr = --tstr; // string end
    while(istr != estr)
    {
        char tmp = *istr;
        *istr = *estr;
        *estr = tmp;
        istr++;
        estr--;
    }
    return str;
}
 
void main()
{
    char* ptr = strdup("rajan");
    char* rstr = str_rev(ptr);
 
}

Important points:

  • if char* ptr=”rajan” is used, the above program will crash since, “rajan” is a const literal present part of code segment which cannot be modified.
  • strdup creates a new pointer from the input const char*. We use that to remove the const
  • free on ptr should be called !!