题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。

题解思路：使用栈或者数组

1. 分割字符串，使用双指针，pre指向空格的下一个不为空格的字符，cur指向当前字符
2. 初始化，pre = 0，指向字符串第一个字符；cur = 0 指向当前字符
3. 如题所示，对字符串进行遍历，当字符为空时，cur指向该空字符的前一个不为空格的字符
4. 如果使用栈容器，则str[cur]开始反向保存；如果使用数组容器，则str[pre]正向保存
5. 遍历完第一个单词之后，保存空格(之前并未保存空格)
6. 字符串的最后一个单词是没有空格的，所有最后需要遍历最后一个单词
7. 字符拼接

图示取自大佬鸠摩罗什，在此引用。图示中采用数组形式

代码，该代码采用栈容器

class Solution {
public:
    string ReverseSentence(string str) {
        if(str.empty()) return "";
        stack<char> s;
        int pre = 0;//指向空格的下一个字符
        int cur = 0;//指向当前字符
        //把nowcoder. a am I中最后一个空格之前的字符全部压入栈中
        for(int i =0;i<str.size();i++){
            if(str[i] == ' '){
                cur = i-1;
                while(cur >= pre){
                    s.push(str[cur]);
                    cur--;
                }
                s.push(str[i]);//最后把空格插入
                pre = i+1;//pre指向空格的下一个字符
            }
        }
        //把空格之前的字符压入栈之后，还要将剩余的字符全部压入栈中
        for(int i = str.size()-1;i >= pre;i--){
            s.push(str[i]);
        }
        string result = "";
        while(!s.empty()){
            result+=s.top();
            s.pop();
        }
        return result;
    }
};
``