Thursday, April 2, 2009

string rotation

Well, given a char * and an integer to rotate it clockwise or counter clockwise, lets c how to rotate it.

Ok. the basic idea to rotate a string counter clockwise is
1 : reverse first n - 1 characters.
2 : reverse the rest of the characters.
3 : reverse the whole string.


Eg:
Consider "hello" and you wanted to rotate it thrice in the counter clockwise direction.
So, here are the stages:
After 1 : "ehllo"
After 2 : "eholl"
After 3 : "llohe"
which is the final answer.

try it out for clockwise rotation before looking at the snippet below. It's fun.



enum
{
SUCCESS,
FAILURE
};


int
reverse(char *in, unsigned int start_index,
unsigned int end_index)
{
char temp;
if (in == NULL || start_index > end_index)
return (FAILURE);
while (start_index < end_index) {
temp = in[start_index];
in[start_index] = in[end_index];
in[end_index] = temp;
start_index++;
end_index--;
}
return (SUCCESS);
}


int
rotate_string(char *rotate_me, unsigned int times,
unsigned int is_clockwise)
{
unsigned int len = 0;

if (rotate_me == NULL)
return (FAILURE);
//initialize the length;
len = strlen(rotate_me);
//if times > len, fix it.
times %= len;
//fix if rotation needs to be clockwise
if (times != 0 && is_clockwise) {
times = len - times;
}
/*
* First, reverse the times - 1 characters.
* Now, reverse times to len - 1
* Finally, reverse the whole string.
*/
if (times > 0 &&
(
reverse(rotate_me, 0, times - 1) == FAILURE ||
reverse(rotate_me, times, len - 1) == FAILURE ||
reverse(rotate_me, 0, len - 1) == FAILURE
)
) {
return (FAILURE);
}

return (SUCCESS);
}


and that's the way it's done :)

No comments:

Post a Comment