翻转单词顺序列

题目的主要信息：

将一个英文语句以单词为单位逆序排放
所有单词之间用一个空格隔开，没有仅含空格的案例

举一反三：

学习完本题的思路你可以解决如下题目：

JZ31. 栈的压入、弹出序列

方法一：两次反转（推荐使用）

思路：

我们需要的是将单词位置反转，也即是单词内部不变，属于字符串部分反转问题。如果将整个字符串反转，单词位置倒是反转了，但是内部次序也改变了，此时就需要将内部再反转回去，因此两次反转可以解决。

具体做法：

step 1：将字符串整体反转。
step 2：遍历反转后的字符串，以空格为界限找到一个单词。
step 3：将每个单词部分反转。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    //字符串反转函数
    private void reverse(char [] c, int l, int h){
        //双指针反转
        while(l < h)
            swap(c, l++, h--);
    }
    //字符交换函数
    private void swap(char [] c, int l, int h){
        char temp = c[l];
        c[l] = c[h];
        c[h] = temp;
    }
    
    public String ReverseSentence(String str) {
        int n = str.length();
        char[] c = str.toCharArray();
        //第一次整体反转
        reverse(c, 0, n - 1);
        for(int i = 0; i < n; i++){
            int j = i;
            //以空格为界找到一个单词
            while(j < n && c[j] != ' ') 
                j++;
            //将这个单词反转
            reverse(c, i, j - 1); 
            i = j;
        }
        return new String(c);
    }
}

C++实现代码：

class Solution {
public:
    string ReverseSentence(string str) {
        int n = str.length();
        //第一次整体反转
        reverse(str.begin(), str.end()); 
        for(int i = 0; i < n; i++){
            int j = i;
            //以空格为界找到一个单词
            while(j < n && str[j] != ' ') 
                j++;
            //将这个单词反转
            reverse(str.begin() + i, str.begin() + j); 
            i = j;
        }
        return str;
    }
};

Python实现代码：

class Solution:
    def ReverseSentence(self , str: str) -> str:
        #第一次整体反转
        str = str[::-1]
        s = str.split(' ')
        #以空格为界部分反转
        return (' '.join(s[i][::-1] for i in range(len(s))))

复杂度分析：

时间复杂度： $O (n)$ ， $n$ 为整个句子字符串的长度，遍历整个字符串和反转字符串都是 $O (n)$
空间复杂度： $O (1)$ ，常数级变量，无额外辅助空间（其中java版本有 $O (n)$ 的辅助空间）

方法二：栈（扩展思路）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。