题目
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
要翻转单词的顺序同时保持单词内字符的顺序，很自然地想到利用栈先进后出的特性。遍历s把单词逐个入栈，然后抛出单词直到栈空，记得在首个单词以外的单词前面加上空格。
时间复杂度O(n)，空间复杂度O(n)。
代码
class Solution {
public:
string reverseWords(string s) {
stack<string> stk;
for(int left = 0; left < s.size(); ++left)
{
if(s[left] != ' ')
{
int right = left;
while(right < s.size() && s[right] != ' ') right++;
string tmp(s.begin() + left, s.begin() + right);
stk.push(tmp);
left = right;
}
}
string ans = "";
while(!stk.empty())
{
if(!ans.empty()) ans += ' ';
ans += stk.top();
stk.pop();
}
return ans;
}
};
改进
用栈解决需要额外O(n)的空间，能不能直接在传入的s上原地修改？利用c++的翻转函数reverse（也可以自己实现）可以做到，先翻转整个字符串，然后用双指针，write指向要写入的位置，read指向读到单词的位置；read读到单词时，用wordend向后遍历到空格或者字符串结束，把wordend遍历到的字符写到write指向的位置，然后再在新字符串离翻转新写进来的这个单词。注意每次写入单词前除了首个单词外要加上空格。
时间复杂度O(n)，空间复杂度O(1)。
代码
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
int write = 0, n = s.size();
for(int read = 0; read < n; ++read)
{
if(s[read] != ' ')
{
if(write != 0) s[write++] = ' ';
int wordend = read;
while(wordend < n && s[wordend] != ' ') s[write++] = s[wordend++];
reverse(s.begin() + write - (wordend - read), s.begin() + write);
read = wordend;
}
}
s.erase(s.begin() + write, s.end());
return s;
}
};