Reverse Words in a Sentence

Problem Statement

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

Hint

• Note how the words are separated by whitespaces

Try it yourself

Solution

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

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 course!