Saturday, August 18, 2012

Reverse a string

Solution #1: 
If extra space is available then copy the string in reverse order to a newly allocated string in O(n) time.

Solution #2: 
Again, if extra space is permissible then we can use a stack to first push the entire string on the stack and then pop it in reverse order.

Solution #3: 
If it has to be done in place, then we can take two pointers at the start and end of the string and can swap the characters they point to while incrementing and decrementing them respectively till they collide.

Solution #4: 
Approach three can also be done recursively as follows

void reverse(char *start, char *end)
{
    char temp;

    if(start >= end)
        return;
    
    temp = start[0];
    start[0] = end[0];
    end[0] = temp;

    reverse(start+1, end-1);    
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    int len;

    gets(str);
    len = strlen(str);

    reverse(str, str+len-1);

    printf("%s\n", str);

    return 1;
}

No comments:

Post a Comment