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

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"

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

Not exactly in place, but anyway: Python:

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

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.

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

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

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.

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!

class Program
{
    static void Main(string[] args)
    {
        string s1 =" My Name varma:;
        string[] arr = s1.Split(' ');
        Array.Reverse(arr);
        string str = string.Join(" ", arr);
        Console.WriteLine(str);
        Console.ReadLine();

    }
}

This is assuming all words are separated by spaces:

#include <stdio.h>
#include <string.h>

int main()
{
    char string[] = "What are you looking at";
    int i, n = strlen(string);
    
    int tail = n-1;
    for(i=n-1;i>=0;i--)
    {
        if(string[i] == ' ' || i == 0)
        {
            int cursor = (i==0? i: i+1);
            while(cursor <= tail)
                printf("%c", string[cursor++]);
            printf(" ");
            tail = i-1;
        }
    }
    return 0;
}

This is not perfect but it works for me right now. I don't know if it has O(n) running time btw (still studying it ^^) but it uses one additional array to fulfill the task.

It is probably not the best answer to your problem because i use a dest string to save the reversed version instead of replacing each words in the source string. The problem is that i use a local stack variable named buf to copy all the words in and i can not copy but into the source string as this would lead to a crash if the source string is const char * type.

But it was my first attempt to write s.th. like this :) Ok enough blablub. here is code:

#include <iostream>
using namespace std;

void reverse(char *des, char * const s);
int main (int argc, const char * argv[])
{    
    char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created";
    char *x = (char*)"Dogfish! White-spotted Shark, Bullhead";

    printf("Before: |%s|\n", x);
    printf("Before: |%s|\n", s);
    
    char *d = (char*)malloc((strlen(s)+1)*sizeof(char));  
    char *i = (char*)malloc((strlen(x)+1)*sizeof(char));
    
    reverse(d,s);
    reverse(i,x);
    
    printf("After: |%s|\n", i);
    printf("After: |%s|\n", d);
    
    free (i);
    free (d);
    
    return 0;
}

void reverse(char *dest, char *const s) {
    // create a temporary pointer
    if (strlen(s)==0) return;
    unsigned long offset = strlen(s)+1;
    
    char *buf = (char*)malloc((offset)*sizeof(char));
    memset(buf, 0, offset);
    
    char *p;
    // iterate from end to begin and count how much words we have
    for (unsigned long i = offset; i != 0; i--) {
        p = s+i;
        // if we discover a whitespace we know that we have a whole word
        if (*p == ' ' || *p == '\0') {
            // we increment the counter
            if (*p != '\0') {
                // we write the word into the buffer
                ++p;
                int d = (int)(strlen(p)-strlen(buf));
                strncat(buf, p, d);
                strcat(buf, " ");
            }
        }
    }
    
    // copy the last word
    p -= 1;
    int d = (int)(strlen(p)-strlen(buf));
    strncat(buf, p, d);
    strcat(buf, "\0");
    
    // copy stuff to destination string
    for (int i = 0; i < offset; ++i) {
        *(dest+i)=*(buf+i);
    }
    
    free(buf);
}

We can insert the string in a stack and when we extract the words, they will be in reverse order.

void ReverseWords(char Arr[])
{
	std::stack<std::string> s;
	char *str;
	int length = strlen(Arr);
	str = new char[length+1];
	std::string ReversedArr;
	str = strtok(Arr," ");
	while(str!= NULL)
    {
		s.push(str);
		str = strtok(NULL," ");
	}
	while(!s.empty())
    {
		ReversedArr = s.top();
		cout << " " << ReversedArr;
		s.pop();
	}
}

This quick program works..not checks the corner cases though.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    char word[50];
    struct node *next;
};
struct stack
{
    struct node *top;
};
void print (struct stack *stk);
void func (struct stack **stk, char *str);
main()
{
    struct stack *stk = NULL;
    char string[500] = "the sun is yellow and the sky is blue";
    printf("\n%s\n", string);
    func (&stk, string);
    print (stk);
}
void func (struct stack **stk, char *str)
{
    char *p1 = str;
    struct node *new = NULL, *list = NULL;
    int i, j;
    if (*stk == NULL)
    {
        *stk = (struct stack*)malloc(sizeof(struct stack));
        if (*stk == NULL)
            printf("\n####### stack is not allocated #####\n");
        (*stk)->top = NULL;
    }
    i = 0;
    while (*(p1+i) != '\0')
    {
        if (*(p1+i) != ' ')
        {
            new = (struct node*)malloc(sizeof(struct node));
            if (new == NULL)
                printf("\n####### new is not allocated #####\n");
            j = 0;
            while (*(p1+i) != ' ' && *(p1+i) != '\0')
            {
                new->word[j] = *(p1 + i);
                i++;
                j++;
            }
            new->word[j++] = ' ';
            new->word[j] = '\0';
            new->next = (*stk)->top;
            (*stk)->top = new;
        }
        i++;
   }
}
void print (struct stack *stk)
{
    struct node *tmp = stk->top;
    int i;
    while (tmp != NULL)
    {
        i = 0;
        while (tmp->word[i] != '\0')
        {
            printf ("%c" , tmp->word[i]);
            i++;
        }
        tmp = tmp->next;
    }
    printf("\n");
}

Most of these answers fail to account for leading and/or trailing spaces in the input string. Consider the case of str=" Hello world"... The simple algo of reversing the whole string and reversing individual words winds up flipping delimiters resulting in f(str) == "world Hello ".

The OP said "I want to reverse the order of the words" and did not mention that leading and trailing spaces should also be flipped! So, although there are a ton of answers already, I'll provide a [hopefully] more correct one in C++:

#include <string>
#include <algorithm>

void strReverseWords_inPlace(std::string &str)
{
  const char delim = ' ';
  std::string::iterator w_begin, w_end;
  if (str.size() == 0)
    return;

  w_begin = str.begin();
  w_end   = str.begin();

  while (w_begin != str.end()) {
    if (w_end == str.end() || *w_end == delim) {
      if (w_begin != w_end)
        std::reverse(w_begin, w_end);
      if (w_end == str.end())
        break;
      else
        w_begin = ++w_end;
    } else {
      ++w_end;
    }
  }

  // instead of reversing str.begin() to str.end(), use two iterators that
  // ...represent the *logical* begin and end, ignoring leading/traling delims
  std::string::iterator str_begin = str.begin(), str_end = str.end();
  while (str_begin != str_end && *str_begin == delim)
    ++str_begin;
  --str_end;
  while (str_end != str_begin && *str_end == delim)
    --str_end;
  ++str_end;
  std::reverse(str_begin, str_end);
}

My version of using stack:

public class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String ns= s.trim();
        Stack<Character> reverse = new Stack<Character>();
        boolean hadspace=false;
        
        //first pass
        for (int i=0; i< ns.length();i++){
        	char c = ns.charAt(i);
        	if (c==' '){
        		if (!hadspace){
        			reverse.push(c);
        			hadspace=true;
        		}
        	}else{
        		hadspace=false;
        		reverse.push(c);
        	}
        }
        Stack<Character> t = new Stack<Character>();
        while (!reverse.empty()){
        	char temp =reverse.pop();
            if(temp==' '){
            	//get the stack content out append to StringBuilder
                while (!t.empty()){
                    char c =t.pop();
                    sb.append(c);
                }
                sb.append(' ');
            }else{
            	//push to stack
                t.push(temp);
            }
        }
        while (!t.empty()){
            char c =t.pop();
            sb.append(c);
        }
        return sb.toString();
    }
}

Store Each word as a string in array then print from end

public void rev2() {
	String str = "my name is ABCD";
	String A[] = str.split(" ");

	for (int i = A.length - 1; i >= 0; i--) {
		if (i != 0) {
			System.out.print(A[i] + " ");
		} else {
			System.out.print(A[i]);
		}
	}

}

In Python, if you can't use [::-1] or reversed(), here is the simple way:

def reverse(text):

  r_text = text.split(" ")
  res = []
  for word in range(len(r_text) - 1, -1, -1): 
    res.append(r_text[word])

  return " ".join(res)

print (reverse("Hello World"))

>> World Hello
[Finished in 0.1s]

Printing words in reverse order of a given statement using C#:

    void ReverseWords(string str)
    {
        int j = 0;
        for (int i = (str.Length - 1); i >= 0; i--)
        {
            if (str[i] == ' ' || i == 0)
            {
                j = i == 0 ? i : i + 1;

                while (j < str.Length && str[j] != ' ')
                    Console.Write(str[j++]);
                Console.Write(' ');
            }
        }
    }

Here is the Java Implementation:

public static String reverseAllWords(String given_string)
{
	if(given_string == null || given_string.isBlank())
		return given_string;

	char[] str = given_string.toCharArray();
	int start = 0;
	
	// Reverse the entire string
	reverseString(str, start, given_string.length() - 1);

	// Reverse the letters of each individual word
	for(int end = 0; end <= given_string.length(); end++)
	{
		if(end == given_string.length() || str[end] == ' ')
		{
			reverseString(str, start, end-1);
			start = end + 1;
		}
	}
	return new String(str);
}

// In-place reverse string method
public static void reverseString(char[] str, int start, int end)
{
	while(start < end)
	{
		char temp = str[start];
		str[start++] = str[end];
		str[end--] = temp;
	}
}

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.

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.

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

import java.util.Scanner;

public class revString {
   static char[] str;

   public static void main(String[] args) {
   	//Initialize string
	//str = new char[] { 'h', 'e', 'l', 'l', 'o', ' ', 'a', ' ', 'w', 'o',
	//'r', 'l', 'd' };
	getInput();
	
	// reverse entire string
	reverse(0, str.length - 1);

	// reverse the words (delimeted by space) back to normal
	int i = 0, j = 0;
	while (j < str.length) {

		if (str[j] == ' ' || j == str.length - 1) {

			int m = i;
			int n;

			//dont include space in the swap. 
			//(special case is end of line)
			if (j == str.length - 1)
				n = j;
			else
				n = j -1;
			
			
			//reuse reverse
			reverse(m, n);

			i = j + 1;

		}
		j++;
	}

	displayArray();
}

private static void reverse(int i, int j) {

	while (i < j) {

		char temp;
		temp = str[i];
		str[i] = str[j];
		str[j] = temp;

		i++;
		j--;
	}
}
private static void getInput() {
	System.out.print("Enter string to reverse: ");
	Scanner scan = new Scanner(System.in);
	str = scan.nextLine().trim().toCharArray(); 
}

private static void displayArray() {
	//Print the array
	for (int i = 0; i < str.length; i++) {
		System.out.print(str[i]);
	}
}

}

It can be done more simple using sscanf:

void revertWords(char *s);
void revertString(char *s, int start, int n);
void revertWordsInString(char *s);

void revertString(char *s, int start, int end)
{
     while(start<end)
     {
         char temp = s[start];
         s[start] = s[end];
         s[end]=temp;
         start++;
         end --;
     }
}


void revertWords(char *s)
{
  int start = 0;

  char *temp = (char *)malloc(strlen(s) + 1);
  int numCharacters = 0;
  while(sscanf(&s[start], "%s", temp) !=EOF)
  {
      numCharacters = strlen(temp);

      revertString(s, start, start+numCharacters -1);
      start = start+numCharacters + 1;
      if(s[start-1] == 0)
      return;

  }
  free (temp);

}

void revertWordsInString(char *s)
{
   revertString(s,0, strlen(s)-1);
   revertWords(s);
}

int main()
{
   char *s= new char [strlen("abc deff gh1 jkl")+1];
   strcpy(s,"abc deff gh1 jkl");
   revertWordsInString(s);
   printf("%s",s);
   return 0;
}

In Java using an additional String (with StringBuilder):

public static final String reverseWordsWithAdditionalStorage(String string) {
    StringBuilder builder = new StringBuilder();
    
    char c = 0;
    int index = 0;
    int last = string.length();
    int length = string.length()-1;
    StringBuilder temp = new StringBuilder();
    for (int i=length; i>=0; i--) {
        c = string.charAt(i);
        if (c == SPACE || i==0) {
            index = (i==0)?0:i+1;
            temp.append(string.substring(index, last));
            if (index!=0) temp.append(c);
            builder.append(temp);
            temp.delete(0, temp.length());
            last = i;
        }
    }
    
    return builder.toString();
}

In Java in-place:

public static final String reverseWordsInPlace(String string) {
    char[] chars = string.toCharArray();
    
    int lengthI = 0;
    int lastI = 0;
    int lengthJ = 0;
    int lastJ = chars.length-1;
    
    int i = 0;
    char iChar = 0;
    char jChar = 0;
    while (i<chars.length && i<=lastJ) {
        iChar = chars[i];
        if (iChar == SPACE) {
            lengthI = i-lastI;
            for (int j=lastJ; j>=i; j--) {
                jChar = chars[j];
                if (jChar == SPACE) {
                    lengthJ = lastJ-j;
                    swapWords(lastI, i-1, j+1, lastJ, chars);
                    lastJ = lastJ-lengthI-1;
                    break;
                }
            }
            lastI = lastI+lengthJ+1;
            i = lastI;
        } else {
            i++;
        }
    }
    
    return String.valueOf(chars);
}

private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) {
    int lengthA = endA-startA+1;
    int lengthB = endB-startB+1;
    
    int length = lengthA;
    if (lengthA>lengthB) length = lengthB;

    int indexA = 0;
    int indexB = 0;
    char c = 0;
    for (int i=0; i<length; i++) {
        indexA = startA+i;
        indexB = startB+i;
        
        c = array[indexB];
        array[indexB] = array[indexA];
        array[indexA] = c;
    }

    if (lengthB>lengthA) {
        length = lengthB-lengthA;
        int end = 0;
        for (int i=0; i<length; i++) {
            end = endB-((length-1)-i);
            c = array[end];
            shiftRight(endA+i,end,array);
            array[endA+1+i] = c;
        }
    } else if (lengthA>lengthB) {
        length = lengthA-lengthB;
        for (int i=0; i<length; i++) {
            c = array[endA];
            shiftLeft(endA,endB,array);
            array[endB+i] = c;
        }
    }
}

private static final void shiftRight(int start, int end, char[] array) {
    for (int i=end; i>start; i--) {
        array[i] = array[i-1];
    }
}

private static final void shiftLeft(int start, int end, char[] array) {
    for (int i=start; i<end; i++) {
        array[i] = array[i+1];
    }
}

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 . . .

Here is a C implementation that is doing the word reversing inlace, and it has O(n) complexity.

char* reverse(char *str, char wordend=0)
{
    char c;
    size_t len = 0;
    if (wordend==0) {
        len = strlen(str);
    }
    else {
        for(size_t i=0;str[i]!=wordend && str[i]!=0;i++)
            len = i+1;
    }
            for(size_t i=0;i<len/2;i++) {
                c = str[i];
                str[i] = str[len-i-1];
                str[len-i-1] = c;
            }
    return str;
}

char* inplace_reverse_words(char *w)
{
    reverse(w); // reverse all letters first
    bool is_word_start = (w[0]!=0x20);

    for(size_t i=0;i<strlen(w);i++){
        if(w[i]!=0x20 && is_word_start) {
            reverse(&w[i], 0x20); // reverse one word only
            is_word_start = false;
        }
        if (!is_word_start && w[i]==0x20) // found new word
            is_word_start = true;
    }
    return w;
}

Better version
Check my blog http://bamaracoulibaly.blogspot.co.uk/2012/04/19-reverse-order-of-words-in-text.html

public string reverseTheWords(string description)
{
	if(!(string.IsNullOrEmpty(description)) && (description.IndexOf(" ") > 1))
    {
		string[] words= description.Split(' ');
		Array.Reverse(words);
		foreach (string word in words)
        {
			string phrase = string.Join(" ", words);
			Console.WriteLine(phrase);
		}
		return phrase;
	}
	return description;
}

public class manip{

public static char[] rev(char[] a,int left,int right) {
	char temp;
	for (int i=0;i<(right - left)/2;i++)	{
		temp = a[i + left];
		a[i + left] = a[right -i -1];
		a[right -i -1] = temp;
	}

	return a;
}
public static void main(String[] args) throws IOException {

	String s= "i think this works";
	char[] str = s.toCharArray();		
	int i=0;
	rev(str,i,s.length());
	int j=0;
	while(j < str.length) {
		if (str[j] != ' ' && j != str.length -1) {
			j++;
		} else
		{
			if (j == (str.length -1))	{
				j++;
			}
			rev(str,i,j);
			i=j+1;
			j=i;
		}
	}
	System.out.println(str);
}

I know there are several correct answers. Here is the one in C that I came up with. This is an implementation of the excepted answer. Time complexity is O(n) and no extra string is used.

#include<stdio.h>

char * strRev(char *str, char tok)
{
   int len = 0, i;
   char *temp = str;
   char swap;

   while(*temp != tok && *temp != '\0') {
      len++; temp++;
   }   
   len--;

   for(i = 0; i < len/2; i++) {
      swap = str[i];
      str[i] = str[len - i]; 
      str[len - i] = swap;
   }   

   // Return pointer to the next token.
   return str + len + 1;
}
                                                                                                                                                                                                                                                                                     
int main(void)
{
   char a[] = "Reverse this string.";
   char *temp = a;

   if (a == NULL)
      return -1; 

   // Reverse whole string character by character.
   strRev(a, '\0');

   // Reverse every word in the string again.
   while(1) {
      temp = strRev(temp, ' ');
      if (*temp == '\0')
         break;

      temp++;
   }   
   printf("Reversed string: %s\n", a); 
   return 0;
}

Usage

char str[50] = {0};
strcpy(str, (char*)"My name is Khan");
reverseWords(str);

Method

void reverseWords(char* pString){
    if(NULL ==pString){
        return;
    }
    int nLen     = strlen(pString);
    reverseString(pString,nLen);
    char* start  = pString;
    char* end    = pString;
    nLen         = 0;
    while (*end) {
        if(*end == ' ' ){
            reverseString(start,nLen);
            end++;
            start = end;
            nLen  = 0;
            continue;
        }
        nLen++;
        end++;
    }
    reverseString(start,nLen);
    printf("\n Reversed: %s",pString);
    
}


void reverseString(char* start,int nLen){
    char* end = start+ nLen-1;
    while(nLen > 0){
        char temp = *start;
        *start    = *end;
        *end      = temp;
        end--;
        start++;
        nLen-=2;
    }
}

This is how you solve it in TCL no matter how many spaces or tabs or new lines (\n) characters exist in your string. this is a real life solution and the human way of thinking. It does not consider one and only one space is a mark of a new word.

And i think in C/C++ and Java you can translate it the same way.

I worked on it for two days before this posting, because i did not accept that there exist functions provided by the library of the language which are also made for us, and we don't use them.

<!-- language: lang-php -->
# 1- Reverse the orignial text
set reversed [ string reverse  $all_original_text] 

# 2- split the reversed string $reversed into a list of words then loop over them
set list_of_reversed_words [split $reversed  ]

foreach reversed_words $list_of_reversed_words {

# 3- find the indices of the extremes of each reversed word in the $reversed

set word_start [ string first $reversed_words $reversed $word_start]
set word_end [ expr $word_start -1 + [string length $letter] ]

# 4- reverse the current-in-the-loop reversed word back to its normal state, e.g: 
# if i have a word "loohcs" then convert it by reversing it to "school"

set original_word [string reverse [ string range $reversed $word_start $word_end] ]

# 5- replace  the reversed word (loohcs) with the correcte one (school)

set reversed [ string replace $reversed $word_start $word_end $original_word]

# 6- set the start-of-search index to the index 
# directly after the ending of the current word

set word_start [expr $word_end +1]

# 7-continue to the next loop  
}

#print the result
puts "finally: $reversed"

public class StringReverse {

  public static void main(String[] args) {
	
	StringReverse sr =new StringReverse();
	String output=sr.reverse("reverse this string");

	String substring="";
	for(int i=0;i<=output.length();i++)
		{
		if(i==output.length()){
			System.out.print(sr.reverse(substring));
			substring="";
		}else if(output.charAt(i)==' ' ){
			System.out.print(sr.reverse(substring+" "));
			substring="";
			
		}
		if(i<output.length())
		{
		substring+=output.charAt(i);}
		}
		
}

public String reverse(String str){
	char[] value=str.toCharArray();
	int count=str.length();
	int n = count - 1;
    for (int j = (n-1) >> 1; j >= 0; --j) {
        char temp = value[j];
        value[j] = value[n - j];
        value[n - j] = temp;
    }
	return new String(value);
  }
}

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

void reverse(char *data, int len) {
	int counter = 0;
	int end = len - 1;
	char temp;

	for (counter = 0; counter < len / 2; counter++, end--) {
		temp = data[counter];
		data[counter] = data[end];
		data[end] = temp;
	}
}

int main(void) {
	char data[] = "This is a line and needs to be reverse by words!";
	int c = 0;
	int len = strlen(data);
	int wl = 0;
	int start = 0;
	printf("\n    data =  %s", data);
	reverse(data, len);

	for (c = 0; c < len; c++) {
		if (!wl) {
			start = c;
		}
		if (data[c] != ' ') {
			wl++;
		} else {
			reverse(data + start, wl);
			wl = 0;
		}

	}

	printf("\nnow data =  %s", data);
	return EXIT_SUCCESS;
}

Using Java :

String newString = "";
String a = "My name is X Y Z";
	int n = a.length();
	int k = n-1;
	int j=0;
	
	for (int i=n-1; i>=0; i--)
	{
		if (a.charAt(i) == ' ' || i==0)
		{

			j= (i!=0)?i+1:i;
			
			while(j<=k)
			{
				newString = newString + a.charAt(j);
				j=j+1;
			}
			newString = newString + " ";
			k=i-1;
		}
		
	}
	System.out.println(newString);

Complexity is O(n) [traversing entire array] + O(n) [traversing each word again] = O(n)

Here's a nice tweak for those who liked the question... what if the alphabet comprising the swapped words is smaller than 16 chars (16 including "space")? there are many examples for such alphabets: the numeric chars [01234567890.-+] , the genome letters [GATC] , the hawaiian alphabet [aeiouhklmnpv?], morse code [-.] , musical notes [ABCDEFG#m], etc. This allows encoding the chars as nibbles (4bits) and storing two encoded chars inside one 8bit char.

It's still not trivial doing the words swap in a single loop with one cursor moves left-to-right and the other right-to-left. There are actually 4 types of word-copying: copy a word from the left string's side to the right, from the right string's side to the left and the two equivalent copies that involves read/write overlapping: position X->X+y and X->X-y, where y is smaller than X's length.

The nice optimization is that during the first half of the loop words from the right side are encoded into the left (preserving the original left values), but then on the second half words from the left can be copied directly to right and then the left chars are rewritten with their final values...

Here's the C code, which takes any alphabet as parameter:

#define WORDS_DELIMITER  ' '
#define UNMAPPED         0xFF

#define BITS_IN_NIBBLE   4
#define BITS_IN_BYTE     8
#define CHARS_IN_NIBBLE  (1 << BITS_IN_NIBBLE)
#define CHARS_IN_BYTE    (1 << BITS_IN_BYTE)

typedef union flip_char_ {
    unsigned char clear;
    struct {
        unsigned char org:4;
        unsigned char new:4;
    } encoded;
} flip_char_t;

typedef struct codec_ {
    unsigned char nibble2ascii[CHARS_IN_NIBBLE];
    unsigned char ascii2nibble[CHARS_IN_BYTE];
} codec_t;

static int 
codec_init (const unsigned char *alphabet, codec_t *codec)
{
size_t len = strlen(alphabet), i;

if (len > CHARS_IN_NIBBLE) {
    fprintf(stderr, "alphabet is too long!\n");
    return -1;
}
if (strchr(alphabet, WORDS_DELIMITER) == NULL) {
    fprintf(stderr, "missing space in the alphabet\n");
    return -1;
}
strcpy(codec->nibble2ascii, alphabet);
memset(codec->ascii2nibble , UNMAPPED, CHARS_IN_BYTE);
for (i=0; i<len; i++) {
    codec->ascii2nibble[ alphabet[i] ] = i;
}
return 0;
}

static inline int
is_legal_char (const codec_t *codec, const unsigned char ch)
{
return codec->ascii2nibble[ch] != UNMAPPED;
}

static inline unsigned char 
encode_char (const codec_t *codec, unsigned char org, unsigned char new)
{
flip_char_t flip;
flip.encoded.org = codec->ascii2nibble[org];
flip.encoded.new = codec->ascii2nibble[new];
return flip.clear;
} 

static inline unsigned char 
decode_org (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.org];
}

static inline unsigned char 
decode_new (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.new];
}

// static void inline
// encode_char (const char *alphabet, const char *
static int 
flip_words (const unsigned char *alphabet, unsigned char *a, size_t len)
{
codec_t codec;     /* mappings of the 16char-alphabet to a nibble */
int r=len-1;       /* right/reader cursor: moves from right to left scanning for words */
int l=0;           /* left/writer cursor: moves from left to right */
int i=0;                      /* word iterator */
int start_word=-1,end_word=-1; /* word boundaries */
unsigned char org_r=0;        /* original value pointed by the right cursor */
int encode=0, rewrite=0;      /* writing states */

if (codec_init(alphabet, &codec) < 0) return -1;

/* parse the buffer from its end backward */
while (r>=0) {
    if (r>=l && !is_legal_char(&codec, a[r])) {
        fprintf(stderr, "illegal char %c in string\n", a[r]);
        return -1;
    }
    /* read the next charachter looking for word boundaries */
    org_r = (r<l) ? decode_org(&codec, a[r]) : a[r];
    /* handle word boundaries */
    if (org_r == WORDS_DELIMITER) {
        /* mark start of word: next char after space after non-space  */ 
        if (end_word>0 && start_word<0) start_word = r/*skip this space*/+1;
        /* rewrite this space if necessary (2nd half) */
        if (r<l) a[r] = decode_new(&codec,a[r]);
    } else {
        /* mark end of word: 1st non-space char after spaces */ 
        if (end_word<0) end_word = r;
        /* left boundary is a word boundary as well */
        if (!r) start_word = r;
    }
    /* Do we have a complete word to process? */
    if (start_word<0 || end_word<0) {
        r--;
        continue;
    }
    /* copy the word into its new location */
    for(i=start_word; i<=end_word; i++, l++) {
        if (i>=l && !is_legal_char(&codec, a[l])) {
            fprintf(stderr, "illegal char %c in string\n", a[l]);
            return -1;
        }
        /* reading phase: value could be encoded or not according to writer's position */
        org_r= (i<l) ? decode_org(&codec, a[i]) : a[i];
        /* overlapping words in shift right: encode and rewrite */
        encode=rewrite=(l>=start_word && l<=end_word && i<l);
        /* 1st half - encode both org and new vals */
        encode|=(start_word-1>l);
        /* 2nd half - decode and rewrite final values */
        rewrite|=(i<l);
        /* writing phase */
        a[l]= encode ? encode_char(&codec, a[l], org_r) : org_r;
        if (rewrite) {
            a[i]=decode_new(&codec, a[i]);
        }
    }
    /* done with this word! */
    start_word=end_word=-1;
    /* write a space delimiter, unless we're at the end */
    if (r) {
        a[l] = l<r ? encode_char(&codec, a[l], WORDS_DELIMITER) : WORDS_DELIMITER;
        l++;
    }
    r--;
}
a[l]=0;
return 0; /* All Done! */
}

The simplest way to do this..

          string inputStr = "My name is X Y Z";
          string outputStr = string.Empty;
          List<string> templist1 = new List<string>();
          templist1 = inputStr.Split(' ').ToList();
           for (int i = templist1.Count- 1 ; i >= 0; i--)
          {
              if (outputStr != string.Empty)
              {
                  outputStr = outputStr + " " + templist1[i];
              }
              else
              {
                  outputStr = templist1[i];
              }
          }

           Console.WriteLine("Reverse of a String is", outputStr);

        Output:
        Z Y X is name My

public class reversewords {

public static void main(String args[])

{
	
String s="my name is nimit goyal";

	char a[]=s.toCharArray();
	int x=s.length();
	int count=0;
	for(int i=s.length()-1 ;i>-1;i--)
	{ 
		if(a[i]==' ' ||i==0)
		{ //System.out.print("hello");
			if(i==0)
			{System.out.print(" ");}
			for(int k=i;k<x;k++)
			{
				System.out.print(a[k]);
				count++;
			}
			x=i;
			
		}count++;
		
	}
	System.out.println("");
	System.out.println("total run =="+count);
}

}

output: goyal nimit is name my

total run ==46

Here is the algorithm:

1. Explode the string with space and make an array of words.
2. Reverse the array.
3. Implode the array by space.

One way to do this is to parse each word of our input string and push it into a LIFO stack.

After whole string is processed, we pop out each word off the stack one by one and append it to a StringBuffer class object, which finally contains the reversed input string.

This is one possible solution in Java using StringTokenizer and Stack class. We need to import java.util.Stack.

public String revString(String input)
{
   StringTokenizer words=new StringTokenizer(input); //Split the string into words
   Stack<String> stack= new Stack<String>();
   while(words.hasMoreTokens())
   {
      stack.push(words.nextElement().toString()); // Push each word of the string onto stack. 
   }
   StringBuilder revString=new StringBuilder();
   while(!stack.empty())
   {
       revString.append(stack.pop()+" ");// pop the top item and append it to revString 
   }
   return revString.toString();
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ReverseString
{
    class Program
    {
        static void Main(string[] args)
        {
            string StringReverse = "";
            int StringLength;
            do
            {
                Console.WriteLine("Enter the String : ");
                string InputString = Console.ReadLine();

                Console.WriteLine("Enter the length : ");
                int InputLength = Convert.ToInt32(Console.ReadLine());

                int NewLength = InputLength;
                InputLength = InputLength - 1;
                int LengthString = InputString.Length;
                int l = LengthString - NewLength;
                StringReverse = "";

                while (InputLength >= 0)
                {
                    StringReverse = StringReverse + InputString[InputLength];
                    InputLength--;
                }

                String substr = InputString.Substring(NewLength, l);

                Console.WriteLine("Reverse  String  Is  {0}", StringReverse + substr);

                Console.WriteLine("\tDo you Want to CONTINUE?\n\t1.YES\n\t2.NO");
                StringLength = Convert.ToInt32(Console.ReadLine());
            } 
            while (StringLength == 1);
        }
    }
}

string = "hello world";
strrev = ""
list = [];
def splitstring(string):
    j = 0;
    for i in range(0,len(string)):
        if(string[i] == " "):
           list.append(string[j:i]);
           j = i+1;
        elif (i+1 == len(string)):
            list.append(string[j:i+1]);

splitstring(string);
for i in list:
    for j in range(len(i)-1,-1,-1):
        strrev += i[j];
    if (i != list[-1]):
        strrev+= " ";
print(list);

print(":%s:" %(strrev));

In JAVA

package Test;

public class test2 {

	public static void main(String[] args){
	
		String str = "my name is fawad X Y Z";
		
		String strf = "";
		String strfinal="";
		
		if (str != ""){
				
		for (int i=0 ; i<=str.length()-1; i++){
		
			strf += str.charAt(str.length() - (i+1));
			
		}
		System.out.println(strf);
		}
		else System.out.println("String is Null");
						
			if (strf != ""){
				String[] temp = strf.split(" ");	
				
				String temp1 = "";
				
				System.out.println(temp.length);
				
				for (int j=0; j<=temp.length-1; j++){
					
					temp1 = temp[j];
															
					if(temp1.length()>1){
					
					for (int k=0; k<=temp1.length()-1; k++){
						
						strfinal += temp1.charAt(temp1.length()-(1+k));
						
					}
					strfinal += " ";
					}
					else strfinal += temp1 + " ";
					
				}
				System.out.println(strfinal);
				
			}
			else System.out.println("String Final is Null");
		}
	}

Output:

Z Y X dawaf si eman ym

Z Y X fawad is name my 

public static void main(String args[]) {
    String str = "My name is X Y Z"; // out put "Z Y X is name My"

    // split
    String[] arr = str.split(" ");
    // reverse word
    String reverse = "";
    for (int i = arr.length - 1; i >= 0; i--) {
        if(i!=0){
            reverse += arr[i]+" ";
        }else{
            reverse += arr[i];
        }
    }

    System.out.println(reverse);

}

I did solve the problem without using extra space used only the original string itself, but I couldn't solve the problem in O(n), the least I could get is O(n square) that's for the worst case scenario.

The way how I implemented -

1. Reverse the whole sentence, char by char.
2. Later iterate the whole sentence but this time reverse each word.

AND THAT'S WHY I GOT THE WORST TIME COMPLEXITY AS O(n sqaure)

Please find the code below in java, hope it helps someone.

class MainClass {
    public static void main(String args[]) {

        String str = "reverse me! also lets check";
        System.out.println("The initial string is  --->> " + str);

        for (int i = 0; i < str.length(); i++) {
            //Keep iterating each letter from one end to another.
            str = str.substring(1, str.length() - i)
                + str.substring(0, 1)
                + str.substring(str.length() - i, str.length());
        }
        System.out.println("The reversed string is ---->> " + str);

        for (int i = 0, j = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' ' || i == (str.length() - 1)) {
                //Just to know the start of each word
                int k = j;

                //the below if condition is for considering the last word.
                if(i == (str.length() - 1)) i++;

                while(j < i) {
                    j++;
                    str = str.substring(0, k)
                        //(i-j) is the length of each word
                        + str.substring(k + 1, (k + 1) + i - j)
                        + str.substring(k, k + 1)
                        + str.substring((k + 1) + i - j, i)
                        + str.substring(i);
                    if(j == i) {
                        //Extra j++ for considering the empty white space
                        j++;
                    }
                }
            }
        }
        System.out.println("The reversed string but not the reversed words is ---->> " + str);

    }
}

This is how to do it in Excel as UDF and in VBA:

Public Function ReverseMe(textToReverse As String, _
          Optional delim As String = " ") As String

    Dim test    As String
    Dim arr     As Variant
    Dim arr2    As Variant
    Dim arrPart As Variant
    Dim cnt     As Long

    arr = Split(textToReverse, ".")
    ReDim arr2(UBound(arr))

    For Each arrPart In arr
        arr2(cnt) = StrReverse(arrPart)
        cnt = cnt + 1
    Next arrPart

    ReverseMe = StrReverse(Join(arr2, "."))

End Function

Public Sub TestMe()

    Debug.Print ReverseMe("veso.dosev.diri.rid", ".")
    Debug.Print ReverseMe("VBA is the best language")

End Sub

This Question is asked in Paytm interview for Java position. I come up with the following solution.

class ReverseStringWord{
public static void main(String[] args) {
	String s="My name is X Y Z";
	StringBuilder result=new StringBuilder();
	StringBuilder str=new StringBuilder();
	for(int i=0;i<s.length();i++){
		if(s.charAt(i)==' '){
			result.insert(0,str+" ");
			str.setLength(0);
		}
		else{
			str.append(s.charAt(i));
			if(i==s.length()-1){
				result.insert(0,str+" ");
			}
		}
	}
	System.out.println(result);
}}

By doing a rotation of the string you can reverse the order of the words without reversing the order of the letters.

As each word is rotated to the end of the string we reduce the amount of the string to be rotated by the length of the word. We then rotate any spaces to in front of the word we just placed at the end and shorten the rotating part of the string by 1 for each space. If the entire string is rotated with out seeing a space we are done.

Here is am implementation in C+. The l variable contains the length of the buf to rotate, and n counts the number of rotations made.

    #include <stdio.h>
    #include <string.h>
    
    int main(char *argv[], int argc)
    {
      char buf[20] = "My name is X Y Z";
      int l = strlen(buf);
      int n = 1;
    
      while (l >= n) {
        unsigned char c = buf[0];
        for (int i = 1; i < l; i++) {
          buf[i-1] = buf[i];
        }
        buf[l - 1] = c;
        if (buf[0] == ' ' || c == ' ') {
          l -= n;
          n = 1;
        } else {
          n++;
        }
      }
    
      printf("%s\n", buf);
    }

The rotation code was purposely left very simple.