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

Answer 2

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

Answer 3

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

Answer 4

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 5

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

Answer 6

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