Reverse Words in a String

Medium· parsing· reversal

Problem

Reverse the order of words in a string, where a word is a run of non-space characters. The input may have leading, trailing or repeated spaces; the output must have words separated by exactly one space and no padding at either end.

Examples

Input: s = " the sky is blue "

Output: "blue is sky the"

Extra spaces are dropped and the four words appear in reverse order.

Constraints

• 1 <= s.length <= 10^4
• s contains letters, digits and spaces
• At least one word is present

Hints & approach

Hint 1

Splitting on whitespace and reversing is the quick version.

Hint 2

For an in-place approach on a character array: reverse the whole string, then reverse each word.

Hint 3

Compact the spaces as you go so that only single separators remain.

Approachtry the hints first

Scan from the end of the string, skipping spaces, and each time you find a word collect its characters and append it to the result with a single space separator. This naturally emits words in reverse order and ignores extra spaces. In languages with mutable strings, the in-place version reverses the whole buffer, reverses each word back, and then squeezes out redundant spaces.

Time O(n) · Space O(n)

← PreviousRotate String Next →String to Integer (atoi)