Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Reverse Words in a Sentence

Explore how to reverse the order of words in a sentence without changing the order of letters within each word. This lesson teaches an in-place method that involves reversing the entire string and then each individual word, achieving linear time and constant space complexity.

We'll cover the following...

Statement

Given a sentence (an array of characters), reverse the order of its words without affecting the order of letters within a given word. All operations must be done in place.

Example

The “Hello World” string should be reversed as “World Hello”.

g a Hello World b World Hello a->b

Here’s another example of reversing words in a sentence:

g a The quick brown fox jumped over the lazy dog. b dog. lazy the over jumped fox brown quick The a->b

Sample input

"Hello world."

Expected output

"world. Hello"

Note: The order of letters in a word isn’t reversed.

Try it yourself

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void ReverseWords(char* sentence) {
	//TODO: Write - Your - Code
}

Solution

We will follow two steps:

  1. Reverse the string.
  2. Traverse the string and reverse each word in place.

Note: In each iteration, keep traversing till a white space or end of text occurs.

Let’s apply this solution to our example:

  • Initial string is:
    • “The quick brown fox jumped over the lazy dog.”.
  • Reverse the string:
    • “.god yzal eht revo depmuj xof nworb kciuq ehT”
  • Reverse each word in-place:
    • “dog. lazy the over jumped fox brown quick The”
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
void StrRev(char* str, char* start, char* end) {
	// Return if string is empty or length of string is less than 2
	if (str == nullptr) {
		return;
	}
	// Swap characters, starting from the two extremes
	// and moving in towards the centre of the string
	while (start < end) {
		if (start != nullptr && end != nullptr){
			char temp = *start;
			*start = *end;
			*end = temp;
		}
		start++;
		end--;
	}
}
void ReverseWords(char* sentence) {
	// Here sentence is a null-terminated string ending with char '\0'.
	if (sentence == nullptr) {
		return;
	}
	// To reverse all words in the string, we will first reverse
	// the string. Now all the words are in the desired location, but
	// in reverse order: "Hello World" -> "dlroW olleH".
	int len = strlen(sentence);
	char* start = sentence;
	char * end = sentence + len - 1;
	StrRev(sentence, start, end);
	// Now, let's iterate the sentence and reverse each word in place.
	// "dlroW olleH" -> "World Hello"
	while (true) {
		// Find the start index of a word while skipping spaces.
		while (start && *start == ' ') {
			start++;
		}
		if (start == nullptr || *start == '\0') {
			break;
		}
		// Find the end index of the word.
		end = start + 1;
		while (end && *end != '\0' && *end != ' ') {
			end++;
		}
		// Let's reverse the word in-place.
		if (end != nullptr){
			StrRev(sentence, start, end - 1);
		}
		start = end;
	}
}
int main() {
	string str_to_reverse1 = "Hello World!";
	cout << "1.    Actual string:   " <<	str_to_reverse1 << endl;
	char* reversed1 = const_cast<char*>(str_to_reverse1.c_str());
	ReverseWords(reversed1);
	string reversed1_str(reversed1);
	cout << "      Reversed string: " << reversed1_str << endl;
	cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;
	string str_to_reverse2 = "The quick brown fox jumped over the lazy dog.";
	cout << "2.    Actual string:   " <<	str_to_reverse2 << endl;
	char* reversed2 = const_cast<char*>(str_to_reverse2.c_str());
	ReverseWords(reversed2);
	string reversed2_str(reversed2);
	cout << "      Reversed string: " << reversed2_str << endl;
	cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;
	
}

Time complexity

The time complexity of this solution is linear, O(n)O(n).

Space complexity

The space complexity of this solution is constant, O(1)O(1).

Note: The solution reverses every word in place, that is, it does not require any extra space.