Reverse the ordering of words in a string

Question

Hi,

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)?

cheers

Answer 1

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

Edit: Just to clarify, 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".

Answer 2

What language? If PHP, you can explode on space, then pass the result to array_reverse.

If its not PHP, you'll have to do something slightly more complex like:

words = aString.split(" ");
for (i = 0; i < words.length; i++) {
    words[i] = words[words.length-i];
}

Answer 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'

Answer 4

Actually, the first answer:

words = aString.split(" ");
for (i = 0; i < words.length; i++) {
    words[i] = words[words.length-i];
}

does not work because it undoes in the second half of the loop the work it did in the first half. So, i < words.length/2 would work, but a clearer example is this:

words = aString.split(" "); // make up a list
i = 0; j = words.length - 1; // find the first and last elements
while (i < j) {
    temp = words[i]; words[i] = words[j]; words[j] = temp; //i.e. swap the elements
    i++; 
    j--;
}

Note: I am not familiar with the PHP syntax, and I have guessed incrementer and decrementer syntax since it seems to be similar to Perl.

Answer 5

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

Answer 6

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

Answer 7

public static String ReverseString(String str)
{
    int word_length = 0;
    String result = "";
    for (int i=0; i<str.Length; i++)
    {
        if (str[i] == ' ')
        {
            result = " " + result;
            word_length = 0;
        } else 
        {
            result = result.Insert(word_length, str[i].ToString());
            word_length++;
        }
    }
    return result;
}

This is C# code.

Answer 8

How about ...

var words = "My name is X Y Z";
var wr = String.Join( " ", words.Split(' ').Reverse().ToArray() );

I guess that's not in-line tho.

Answer 9

In c, this is how you might do it, O(N) and only using O(1) data structures (i.e. a char).

#include<stdio.h>
#include<stdlib.h>
main(){
  char* a = malloc(1000);
  fscanf(stdin, "%[^\0\n]", a);
  int x = 0, y;
  while(a[x]!='\0')
  {
    if (a[x]==' ' || a[x]=='\n')
    {
      x++;
    }
    else
    {
      y=x;
      while(a[y]!='\0' && a[y]!=' ' && a[y]!='\n')
      { 
        y++;
      }
      int z=y;
      while(x<y)
      {
        y--;
        char c=a[x];a[x]=a[y];a[y]=c; 
        x++;
      }
      x=z;
    }
  }

  fprintf(stdout,a);
  return 0;
}