题目主要信息

1、对字符串单词进行倒排

2、要求

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

##方法一：暴力

具体方法

首先遍历字符串，当遇到是大小写字符的时候放入临时变量temp中

如果遇到非大小写，就判断temp长度是否大于0，如果大于0就将其放入ArrayList中，最后逆序输出即可。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        ArrayList<String> result = new ArrayList<>();
        String temp = "";
        for (int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if((c >='a' && c<='z') || (c>='A' && c<='Z') ){
                temp += c;
            }else {
                if(temp.length()>0){
                    result.add(temp);
                    temp = "";
                }
            }
        }
        if(temp.length()>0){
            result.add(temp);
        }

        for(int i=result.size()-1;i>=0;i--){
            if(i == 0)
                System.out.print(result.get(i));
            else
            System.out.print(result.get(i)+" ");
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，需要遍历字符串多次，但只有一层for循环
• 空间复杂度：O(n)，一个零时存结果的List。

方法二：正则表达式

具体做法

用正则表达式匹配非字母字符作为分割，分割出来的单词存入数组，然后逆序遍历数组输出即可。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //只匹配字母
        String []split = bf.readLine().split("[^a-zA-Z]+");
        StringBuilder result = new StringBuilder();
        for (int i = split.length - 1; i >= 0; i--)
            result.append(split[i] + " ");
        System.out.println(result.toString().trim());
    }
}

复杂度分析

• 时间复杂度：O(n)，正则表达式的时间
• 空间复杂度：O(n)，分割后的数组长度