# 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 pointersvoid 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;
}
```

1. Mihailik says:

A lot simler in .NET it is:

static string ReverseWords(string str)

{

string[] words = str.Split(‘ ‘);

Array.Reverse(words);

return string.Join(" ", words);

}

2. Nope the .NET solution won’t work as that is not constant space. E.g. your split will create 10 strings if there are 10 words on the stack.

Even C++ stl classes support tokenize kind of calls but we couldn’t use them for the above mentioned problem.

3. Foxfire says:

Well, probably a good solution if you really need constant space. Other than that the solution is horrible as it will

a) totally destroy cache locality (for long strings)

b) not take adavantage of anything better than 8bit processors.

c) perform way too much reads and writes

4. Woof says:

Why is it that developers are frequently know-it-all dillholes?

@Oleg

What is the specification of the problem? CONSTANT SPACE.

@Foxfire

"… probably a good solution if you really need constant space …"

What is the specification of the problem? CONSTANT SPACE. So, yeah, Foxfire, if he said CONSTANT SPACE, he probably really needs it.

Performs way too many reads and writes? From where? Main memory? Where would you put the data? Everything on the stack? Optimize with assembler?

God, I just want to beat the living hell out of you right now.

5. FnH says:

Since this is supposed to run in a memory-constrained space, what about lowering the constant a bit?

while(c1 < c2) {

char ch = *c1;

*c1++ = *c2;

*c2– = ch;

}

can be written as

while(c1 < c2) {

*c1 ^= *c2;

*c2 ^= *c1;

*c1++ ^= *c2–;

}

saving you a byte of memory…

For another 4 bytes, find the end of the string yourself using a single pointer instead of using strlen which needs a 4-byte integer.

Now you’re down to two char*’s … I would be surprised if there is a solution that uses less than that …

6. senfo says:

Woof, you’re taking this waaaay too seriously!

7. OJ says:

@FnH:

*c1 ^= *c2; // bites the dust if *c1 == *c2

Don’t swap unless the characters are different. Otherwise you end up with nada! 🙂

8. chuck says:

The solution does not handle multiple spaces between words or trailing spaces correctly. It will move some trailing or extra spaces one word to the right when the word characters are reversed. This loop works better:

char *c1 = str, *c2 = c1;

while(!*c2) {

for(;*c1 == ‘ ‘ && *c1; c1++, c2++);

if(!*c1) break;

// find word boundary

for(;*c2 != ‘ ‘ && *c2; c2++);

// reverse each word

Reverse(c1, c2 – 1);

c1 = c2;

}

9. FnH says:

@OJ

Sure it is …

/* Suppose both characters are the same … */

assert(*c1 == x && *c2 == x);

*c1 ^= *c2;

assert(*c1 == 0);

assert(*c2 == x);

*c2 ^= *c1;

assert(*c1 == 0)

assert(*c2 == x)

/* removed the advancing of the pointers for illustrative purposes */

*c1 ^= *c2;

assert(*c1 == x);

assert(*c2 == x);

For a formal proof see http://en.wikipedia.org/wiki/XOR_swap_algorithm

10. FnH says:

@OJ:

The problem you probably wanted to point out was that there is a problem if c1 == c2 (*c1 == *c2 isn’t a problem, as pointed out above)

However, if c1 == c2, you never enter the while loop and never try to perform the swap … no bug to see here … please move along …

11. I was just waiting for someone to give the XOR swap 🙂

12. SYY says:

hmm…what about tokenizing every single word using strtok and printing it in reverse order? how do i go about doing it?

13. Here&#39;s another problem which was given to me by Amit . I had lots of fun solving this 🙂 Consider

14. Zaan says:

I ppl!. I need sum help pls.

It just past a time since I code in C, C++ but when i tried this example, it throws me an exception of Access Violation of Memory  at: *pStr = *rightPtr; and *rightPtr = buffer;.

Am I missing something or I just code too much C# :P. Thanks a lot ppl.

//Reverse a String

char * reverseStr( char * pStr)

{

//Get the length of string

int lenStr = strlen(pStr);

//Have a pointer in the end of my buffer

char * rightPtr = (pStr + lenStr) – 1;

//Loop through the string

while(*pStr!=’’)

{

//Create a buffer

char buffer = *pStr;

*pStr = *rightPtr;

//coping reversed str to buffer

*rightPtr = buffer;

//moving pointers

rightPtr–;

pStr++;

}

return pStr;

}

15. Paco says:

how to make "Jose rizal" as "esoj Lazir"?pls answr

16. Paco says:

how to make "Jose rizal" as "esoj Lazir"?pls answr

17. Sasha says:

I found this site where they offer two versions for reversing string order and words –

http://bit.ly/9szt8K

18. Shaan says:

static void Reverse(char[] str)

{

char tmp;

for (int i = 0, j = str.Length – 1; i < j; i++, j–)

{

tmp = str[i];

str[i] = str[j];

str[j] = tmp;

}

}

19. Tracy says:

actually,i might spot a bug in your code,assume the original string is "abc "(note that the last char is a space),then we should output " abc"(note that the space is the firstt char).Unfortunately,your program outputs "abc "(space is still at the last position),presumably,you just have to modify it a little bit,firstly find the fist non-space char and assign its pointer value to c1,then c2=c1+1; after that,it is ok for you to proceed with your existing do while loop. Please correct me if i have got any mistakes. My Email is xiejingf@gmail.com

20. Bijaya Ojha says:

class Program

{

static void Main(string[] args)

{

string x = "bijaya kumar ojha";

string[] y = x.Split(' ');

string rev = string.Empty ;

int a = y.Length;

foreach (var item in y)

{

rev = rev + " " +y[a-1] ;

a–;

}

Console.WriteLine(rev);