159. Reverse Words in a Sentence

Given a string s containing words separated by spaces, return a new string where the words appear in reverse order.

- Multiple leading, trailing, or intermediate spaces should be collapsed.
- The returned string must not have leading or trailing spaces.
- Words in the output must be separated by a single space.

Input: A single string s (may have extra spaces).

Output: A string with words in reversed order, single-space separated, no leading/trailing spaces.

Examples

Input: the quick brown fox
Output: fox brown quick the
Explanation: Words reversed: ['the','quick','brown','fox'] → ['fox','brown','quick','the'] → 'fox brown quick the'.

Input:   hello world  
Output: world hello
Explanation: Leading/trailing spaces stripped; words: ['hello','world'] → reversed → 'world hello'.

Input: a good   example
Output: example good a
Explanation: Extra spaces between words are collapsed; reversed → 'example good a'.

Constraints

• 0 <= s.length <= 10^4
• s contains English letters, digits, and spaces
• There is at least one word

Asked by