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 <= 104
- s 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?
题目：将给定字符串的单词顺序反序，但单词内部字符顺序不变。
思路：其实很简单的全部反序加每个单词单独反序即可。但题目中可能存在多个空格，要求去除这些空格，而且题目需要不增加额外的空间（C++的string data type 是 mutable的）。所以先双指针遍历一遍去除空格，然后再反序。
代码：
class Solution {
public:
string reverseWords(string s) {
int i = 0, j = 0, l = s.length();
while(j < s.length()){
if(s[j] == ' ' && (i==0 || s[i-1] == ' ')){
j++;
} else {
s[i++] = s[j++];
}
}
for(; i 0 && s.back() == ' ') s.pop_back();
reverse(s.begin(), s.end());
i = 0;
while(i < s.length()){
int pos = s.find(' ', i);
if(pos == -1) pos = s.length();
reverse(s.begin()+i, s.begin()+pos);
i = pos+1;
}
return s;
}
};
time: O(N), space:O(1)
