Reverse Words in a String

Given a string s, reverse the order of the words in the string.

A word is a sequence of non-space characters.

The returned string should:

• Contain the words in reverse order.
• Have only a single space between words.
• Have no leading or trailing spaces.

Example

Input:

"the sky is blue"

Reverse the order of the words:

blue is sky the

Output

"blue is sky the"

Main Idea

The simplest approach is:

1. Remove extra spaces.
2. Split the string into words.
3. Reverse the order of the words.
4. Join them using a single space.

For example:

"  hello   world  "

After removing unnecessary spaces:

hello world

Reverse the words:

world hello

Optimized Approach

We can also solve it using O(1) extra space apart from the output representation:

1. Remove extra spaces.
2. Reverse the entire string.
3. Reverse each individual word.

Example:

the sky is blue

Reverse entire string:

eulb si yks eht

Reverse each word:

blue is sky the