Reverse the ordering of words in a string

Question

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

Answer 1

In Python...

ip = "My name is X Y Z"
words = ip.split()
words.reverse()
print ' '.join(words)

Anyway cookamunga provided good inline solution using python!

Answer 2

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 3

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 4

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 5

c# solution to reverse words in a sentence

using System;
class helloworld {
    public void ReverseString(String[] words) {
        int end = words.Length-1;
        for (int start = 0; start < end; start++) {
            String tempc;
            if (start < end ) {
                tempc = words[start];
                words[start] = words[end];
                words[end--] = tempc;
            }
        }
        foreach (String s1 in words) {
            Console.Write("{0} ",s1);
        }
    }
}
class reverse {
    static void Main() {
        string s= "beauty lies in the heart of the peaople";
        String[] sent_char=s.Split(' ');
        helloworld h1 = new helloworld();
        h1.ReverseString(sent_char);
    }
}

output: peaople the of heart the in lies beauty Press any key to continue . . .

Answer 6

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.