Solution: Reverse Words in a String

Statement

You are given a string sentence that may contain leading or trailing spaces, as well as multiple spaces between words. Your task is to reverse the order of the words in the sentence without changing the order of characters within each word. Return the resulting modified sentence as a single string with words separated by a single space, and no leading or trailing spaces.

Note: A word is defined as a continuous sequence of non-space characters. Multiple words separated by single spaces form a valid English sentence. Therefore, ensure there is only a single space between any two words in the returned string, with no leading, trailing, or extra spaces.

Constraints:

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

• There is at least one word in a sentence.

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

Solution

To reverse the words in a sentence, we first remove any extra spaces at the beginning and end to ensure we only deal with the words. Then, we extract all the words in a separate list. This step is helpful because strings are immutable, meaning we can’t change them directly. By working with a list, which is mutable, we can easily process the words.

Next, we use two pointers to work from both ends of the list of words. One pointer starts from the beginning, and the other starts from the end. We swap the words at these two positions, then move the first pointer forward and the second pointer backward, continuing this process until all the words are reversed. Extracting words in a list helped us easily swap elements without creating new strings each time.

Finally, we combine the words with a single space between each, resulting in the sentence with its words in the correct reversed order. The method ensures that there is no unnecessary space before the first word or after the last word, and only one space separates each word. Return the reversed sentence.

Here’s how we can implement the approach above:

• Remove any extra spaces from the beginning and end of the sentence.

• Split the sentence into words based on spaces, and store it in the list result. This automatically removes multiple spaces between words.

• Initialize two pointers:

  • The left pointer starts from the first word in result, index 0.

  • The right pointer starts from the last word in result.

• Next, we iterate over result until the left pointer becomes greater than or equal to the right pointer. In each iteration:

  • Swap the words at positions left and right.

  • Increment the left pointer by 1 to move it one step forward.

  • Decrement the right pointer by 1 to move it one step backward.

• Join the words in result into a sentence with a single space between each word. Return the final reversed sentence.

The following illustration shows these steps in detail: