# Problem Statement

Reverse the order of words in a given sentence (a string of words).

<br>

## Hint
* Note how the words are separated by whitespaces

<br>

## Try it yourself

def reverse_words(sentence):    # sentence here is a string of words
  #TODO: Write - Your - Code
  return sentence

import os, sys
from sys import stdout
from array import *
import random

def getArray(t):
  s = array('u', t)
  s.append('\0')
  return s


def get_my_Array(s):  
  res = ""
  i = 0
  while s[i] != '\0':
    res += s[i]
    i += 1
  return res

Python

class ReverseWords{
  public static String reverseWords (String sentence) {
      //TODO: Write - Your - Code
      return sentence;
  }   
}  

Java

string reverseWords(string sentence) {
  //TODO: Write - Your - Code
  return sentence;
}

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;

let reverseWords = function(sentence) {     // sentence here is an array of characters
  //TODO: Write - Your - Code
    return sentence;
};

JavaScript

def reverse_words(sentence)           # sentence here is an array of characters
  #TODO: Write - Your - Code
  return sentence
end

def replaceAt(string, index, character)
  return string[0, index] + character + string[index + character.length .. -1]
end

def create_random_int_array(length)
  arr = []
  length.times do |i|
    arr << rand(1000)
  end
  return arr
end
# print create_random_int_array(5)

def print_list(arr)
  print "#{arr}\n"
end
# print_list(create_random_int_array(5))

def is_equal(arr1, arr2)
  arr1 == arr2
end
# print is_equal([1,2,3], [1,2,3])

class Pair
  attr_accessor :first, :second
  def initialize(first, second)
    @first, @second = first, second
  end
end
# print Pair.new(2,3).first
# print Pair.new(2,3).second

Ruby

import re

def reverse_words(sentence):
    sentence = re.sub(' +', ' ', sentence.strip())

    sentence = list(sentence)
    str_len = len(sentence)

    str_rev(sentence, 0, str_len - 1)
    start = 0

    for end in range(0, str_len + 1):
        if end == str_len or sentence[end] == ' ':
            str_rev(sentence, start, end - 1)
            start = end + 1

    return ''.join(sentence)

def str_rev(_str, start_rev, end_rev):
    while start_rev < end_rev:
        _str[start_rev], _str[end_rev] = _str[end_rev], _str[start_rev]
        start_rev += 1
        end_rev -= 1

s = 'Hello World!'
print(s)
print(reverse_words(s))

class ReverseWords {
  // Null terminating strings are not used in java
  public static String reverseWords(String sentence) {
        sentence = sentence.trim().replaceAll(" +", " ");

        char[] sentenceArray = sentence.toCharArray();
        int strLen = sentenceArray.length;

        strRev(sentenceArray, 0, strLen - 1);
        int start = 0;

        for (int end = 0; end <= strLen; end++) {
            if (end == strLen || sentenceArray[end] == ' ') {
                strRev(sentenceArray, start, end - 1);
                start = end + 1;
            }
        }

        return new String(sentenceArray);
    }

    public static void strRev(char[] str, int startRev, int endRev) {
        while (startRev < endRev) {
            char temp = str[startRev];
            str[startRev] = str[endRev];
            str[endRev] = temp;
            startRev++;
            endRev--;
        }
    }

  public static void main(String[] args) {
    String s = "Hello World!";
    System.out.println(s);
    System.out.println(reverseWords(s));
  }
}

#include <iostream>
#include <algorithm>
#include <regex>

using namespace std;

void strRev(string &str, int startRev, int endRev) {
    while (startRev < endRev) {
        swap(str[startRev], str[endRev]);
        startRev++;
        endRev--;
    }
}

string reverseWords(string sentence) {
    // Remove leading and trailing spaces
    sentence = regex_replace(sentence, regex("^ +| +$|( ) +"), "$1");

    int strLen = sentence.length();

    // Reverse the entire string
    strRev(sentence, 0, strLen - 1);
    int start = 0;

    for (int end = 0; end <= strLen; end++) {
        if (end == strLen || sentence[end] == ' ') {
            // Reverse each word
            strRev(sentence, start, end - 1);
            start = end + 1;
        }
    }

    return sentence;
}

int main() {

  string str = "Hello World!";
  cout << str << endl;
  cout << reverseWords(str);
}

def reverse_words(sentence)
  sentence = sentence.strip.gsub(/\s+/, ' ')

  sentence = sentence.chars
  str_len = sentence.length

  str_rev(sentence, 0, str_len - 1)
  start = 0

  (0..str_len).each do |end_idx|
    if end_idx == str_len || sentence[end_idx] == ' '
      str_rev(sentence, start, end_idx - 1)
      start = end_idx + 1
    end
  end

  sentence.join('')
end

def str_rev(str, start_rev, end_rev)
  while start_rev < end_rev
    str[start_rev], str[end_rev] = str[end_rev], str[start_rev]
    start_rev += 1
    end_rev -= 1
  end
end

# Test the function
string_to_reverse = "Hello World!"
result = reverse_words(string_to_reverse)

puts "#{string_to_reverse}"
puts "#{result}"

## Solution Explanation
### Runtime complexity
The runtime complexity of this solution is linear, $O(n)$.



### Memory complexity
The memory complexity of this solution is constant, $O(1)$.

<br>

### Solution Breakdown
The essence of this algorithm is to reverse the words in a string by a two-step method using two pointers, effectively manipulating the string in place. Initially, the entire string is reversed, which correctly repositions the words in reverse order. However, due to this reversal of the string, the corresponding characters of words are also reversed. To correct the order of the characters, iterate through the string, and identify the start and end of each word, considering space as a delimiter between words. Set two pointers at the start and end of the word to reverse the characters within that word. By repeating this process for each word, the method effectively achieves the goal without requiring additional memory.
1. Convert the string, `sentence`, into a list of characters and store it back in `sentence`.
2. Get the length of the `sentence` and store it in `str_len`.
3. Define a `str_rev` function to reverse the entire list of characters `sentence`.
4. Set the `start` pointer start to 0 and iterate over the range from 0 to `str_len + 1` using the pointer `end`.
   - When encountering a space or reaching the end of a word, reverse the characters of the word using the `str_rev` function with sentence, `start`, and `end - 1` as arguments.
   - Update the start pointer `start` to `end + 1`.
5. Join the list of characters back into a string using `join(sentence)`.
6. Return the reversed string.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given a sentence (an array of characters), reverse the order of words.

Reverse Words in a Sentence

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime complexity

Memory complexity

Solution Breakdown