题目的主要信息：

• 对字符串中的所有单词进行倒排
• 构成单词的字符只有26个大写或小写英文字母，非构成单词的字符均视为单词间隔符
• 要求倒排后的单词间隔符以一个空格表示，如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符
• 每个单词最长20个字母

方法一：正向统计，逆序输出

具体做法：

我们正向遍历整个字符串，并用一个临时遍历记录单词，遇到字母就将其加到字符串末尾，不停拼接成单词，遇到非字母就看如果这个临时变量不为空，说明刚刚结束单词拼接，这是一个间隔符，我们将这个单词加入output数组末尾，同时临时变量置为空；如果临时变量为空说明它在前面被置空了，前面就是间隔符这个也是，这个忽略掉。最后我们将得到的数组逆序输出即可。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){
    string s;
    while(getline(cin, s)){
        vector<string> output;
        output.clear();
        string temp = "";
        for(int i = 0; i < s.length(); i++){
            if(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z') //字母
                temp += s[i]; //单词拼接
            else{ //非字母，如果有单词才加入数组，没有说明前面是多个其他符号，忽略
                if(temp.length() > 0){ //前面是记录了单词的
                    output.push_back(temp);  //单词加入数组
                    temp = ""; //置空，重新添加字母
                }
            }
        }
        if(temp.length() > 0)
            output.push_back(temp); //最后一个单词
        for(int i = output.size() - 1; i >= 0; i--) //逆序输出
            cout << output[i] << " ";
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串的长度，遍历整个字符串，得到的数组肯定小于等于这个数，因此遍历数组逆序输出时更小，忽略
• 空间复杂度：$O(n)O(n)$，最坏情况下输出的数组长度为$nn$

方法二：正则表达式分割

具体做法：

我们也可以用正则表达式匹配非字母字符作为分割，分割出来的单词存入数组，然后逆序遍历数组，将其连接起来，并在每个单词后面添加一个空格符号。

import java.util.*;
public class Main {

    public Main() {
    }
    
    public static void main(String[] args) {
        Main solution = new Main();
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) { //连续输入
            String str = in.nextLine();  
            System.out.println(solution.reverse(str)); //经过倒排得到输出
        }
    } 
    
    public String reverse(String str) { 
        String[] words = str.split("[^A-Za-z]"); // 匹配非字母的字符进行分割
        StringBuilder res = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) // 逆序添加分割完的单词并加入空格分隔
            res.append(words[i]).append(" ");
        return res.toString().trim();
    }
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，正则表达式匹配分割也是$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，记录分割后单词的数组最长为$nn$