Reverse string
A friend of mine forwarded me this nice little problem he got asked in some interview.
Write code to reverse a string such that the words are reversed as in "We apologise for the inconvenience" becomes "inconvenience the for apologise We".
Obviously (is there fun otherwise?) the problem had to be solved for a memory constraint device (constant space).
I thought I'd share the solution as its kind of neat.
The solution is to do it in two passes. In the first pass the whole string is reversed and in the second each word is reversed again.
After reversing the whole string: "ecneinevnocni eht rof esigolopa eW"
Reversing word at a time: "inconvenience eht rof esigolopa eW"
...
Finally: "inconvenience the for apologise We"
A simple version of code (non-Unicode and considering only space as an word separator) doing this is as follows
// reverses text in between two pointers
void Reverse(char *c1, char *c2)
{
while(c1 < c2) {
char ch = *c1;
*c1++ = *c2;
*c2-- = ch;
}
}
// reverses the complete string
void Reverse(char *str)
{
if (!str) return;
printf("'%s' ===> ", str);
if(strlen(str) > 0) {
// get the complete string reversed in pass 1
Reverse(str, str + strlen(str) - 1);
char *c1 = str, *c2 = str + 1;
do {
// find word boundary
for(;*c2 != ' ' && *c2; c2++);
// reverse each word
Reverse(c1, c2 - 1);
if (!*c2) break; // reached end of string
c1 = ++c2;
}while(*c2);
}
printf("'%s'\n", str);
return;
}
