Solution: Reverse Words in a String

Statement

Given a sentenceA sentence is a string of space-separated words., reverse the order of its wordsA word is a string of characters without any spaces. without affecting the order of letters within the given word.

Constraints:

• The sentence contains English uppercase and lowercase letters, digits, and spaces.

• $1 \leq$ sentence.length $\leq 10^4$

• The order of the letters within a word is not to be reversed.

Note: The input string may contain leading or trailing spaces or multiple spaces between words. The returned string, however, should only have a single space separating each word. Do not include any extra spaces.

Solution

The essence of this algorithm is to reverse the words in a string by utilizing a two-step method using two pointers, effectively manipulating the string in place. The entire string is initially reversed, which correctly repositions the words in reverse order. But 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.

Note: The solution mimics an in-place reversal by converting the string to a mutable list of characters, modifying it in place, and then joining it back into a string.

Now let’s look at an example to understand the detailed workflow of this algorithm:

1. Reverse the entire string: First, we reverse the entire string. This action places the words in the desired order, but each word is itself reversed (i.e., the characters in each word are in the reverse order).