Share via

Reverse string

  • Article

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;
}

Comments

  • Anonymous
    August 01, 2007
    A lot simler in .NET it is: static string ReverseWords(string str) {  string[] words = str.Split(' ');  Array.Reverse(words);  return string.Join(" ", words); }

  • Anonymous
    August 01, 2007
    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.

  • Anonymous
    August 02, 2007
    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

  • Anonymous
    August 04, 2007
    The comment has been removed

  • Anonymous
    August 04, 2007
    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 ...

  • Anonymous
    August 04, 2007
    Woof, you're taking this waaaay too seriously!

  • Anonymous
    August 04, 2007
    The comment has been removed

  • Anonymous
    August 05, 2007
    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; }

  • Anonymous
    August 05, 2007
    @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

  • Anonymous
    August 05, 2007
    @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 ...

  • Anonymous
    August 05, 2007
    I was just waiting for someone to give the XOR swap :)

  • Anonymous
    August 09, 2007
    hmm...what about tokenizing every single word using strtok and printing it in reverse order? how do i go about doing it?

  • Anonymous
    August 15, 2007
    Here&#39;s another problem which was given to me by Amit . I had lots of fun solving this :) Consider

  • Anonymous
    September 04, 2007
    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; }

  • Anonymous
    August 06, 2008
    how to make "Jose rizal" as "esoj Lazir"?pls answr

  • Anonymous
    August 06, 2008
    how to make "Jose rizal" as "esoj Lazir"?pls answr

  • Anonymous
    April 19, 2010
    I found this site where they offer two versions for reversing string order and words - http://bit.ly/9szt8K

  • Anonymous
    September 06, 2010
           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;            }        }

  • Anonymous
    October 23, 2010
    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

  • Anonymous
    April 13, 2013
    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);                      Console.ReadLine();        }    }