151. Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multIPle spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue" Output: "blue is sky the"

Example 2:

Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multIPle spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 104s contains English letters (upper-case and lower-case), digits, and spaces .There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

注意：

        1.需要删除多余空格，但是每个单词之间又需要一个空格

        2.总体思路：先把多余空格删除，再把整个字符串反转，再依次把每一个单词反转

        3.reverse函数很简单，不过多赘述

        4.removeExtraSpace函数：使用快慢指针，重点是当fast所在位置不为空格且slow>0就需要手动添加一个空格。