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 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. This approach involves trimming unnecessary whitespace and splitting the string into individual words, then reversing the order of those words in the list using a two pointer technique.

The two pointers, left and right, are initialized at the beginning and end of the list, respectively, and gradually move inward as they swap words. This swapping process ensures that the first word is moved to the end, the last word is moved to the beginning, and so on, until all the words are in their correct reverse order. Finally, the reversed list is joined back into a string using single spaces.

Here’s how we can implement the approach above:

1. We remove any leading or trailing spaces from the input string sentence. This ensures that unnecessary whitespace at the beginning and end of the string is eliminated.

2. Next, we split the updated sentence into a list of words and store it in result. This method automatically removes multiple spaces between words, ensuring that words are properly separated.

3. We then initialize two pointers:

   1. left: initially set to $0$, pointing to the first word in result.

   2. right: pointing to the last word in result.

4. Next, we iterate over result until the left pointer becomes greater than or equal to the right pointer.

   1. In each iteration, we swap the words at positions left and right to reverse their order.

   2. After swapping, we increment left by $1$ to move to the right and decrement right by $1$ to move to the left.

   3. The above process continues until left is no longer less than right, ensuring that all words are swapped.

5. The final result is returned, containing words in the correct order with single spaces separating them.

The following illustration shows these steps in detail: