Reverse the ordering of words in a string

I have this string s1 = "My name is X Y Z" and I want to reverse the order of the words so that s1 = "Z Y X is name My".

I can do it using an additional array. I thought hard but is it possible to do it inplace (without using additional data structures) and with the time complexity being O(n)?


Solution 1:

Reverse the entire string, then reverse the letters of each individual word.

After the first pass the string will be

s1 = "Z Y X si eman yM"

and after the second pass it will be

s1 = "Z Y X is name My"

Solution 2:

reverse the string and then, in a second pass, reverse each word...

in c#, completely in-place without additional arrays:

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        //reverse complete phrase
        in_text = ReverseString(in_text, 0, rindex);

        //reverse each word in resultant reversed phrase
        for (rindex = 0; rindex <= in_text.Length; rindex++)
        {
            if (rindex == in_text.Length || in_text[rindex] == ' ')
            {
                in_text = ReverseString(in_text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return in_text;
}

static char[] ReverseString(char[] intext, int lindex, int rindex)
{
    char tempc;
    while (lindex < rindex)
    {
        tempc = intext[lindex];
        intext[lindex++] = intext[rindex];
        intext[rindex--] = tempc;
    }
    return intext;
}

Solution 3:

Not exactly in place, but anyway: Python:

>>> a = "These pretzels are making me thirsty"
>>> " ".join(a.split()[::-1])
'thirsty me making are pretzels These'

Solution 4:

In Smalltalk:

'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a]

I know noone cares about Smalltalk, but it's so beautiful to me.

Solution 5:

You cannot do the reversal without at least some extra data structure. I think the smallest structure would be a single character as a buffer while you swap letters. It can still be considered "in place", but it's not completely "extra data structure free".

Below is code implementing what Bill the Lizard describes:

string words = "this is a test";

// Reverse the entire string
for(int i = 0; i < strlen(words) / 2; ++i) {
  char temp = words[i];
  words[i] = words[strlen(words) - i];
  words[strlen(words) - i] = temp;
}

// Reverse each word
for(int i = 0; i < strlen(words); ++i) {
  int wordstart = -1;
  int wordend = -1;
  if(words[i] != ' ') {
    wordstart = i;
    for(int j = wordstart; j < strlen(words); ++j) {
      if(words[j] == ' ') {
        wordend = j - 1;
        break;
      }
    }
    if(wordend == -1)
      wordend = strlen(words);
    for(int j = wordstart ; j <= (wordend + wordstart) / 2 ; ++j) {
      char temp = words[j];
      words[j] = words[wordend - (j - wordstart)];
      words[wordend - (j - wordstart)] = temp;
    }
    i = wordend;
  }
}