描述

反转单词序列

数据范围：1 <= n <= 100

进阶：空间复杂度O(n)，时间复杂度O(n)，保证没有只包含空格的字符串

示例：

• 输入："nowcoder. a am I"
• 输出："I am a nowcoder."

类似题目：字符串变形，反转之后还需要大小写转换

大小写转换方法：

//使用`Character`类方法
    char swapCase1(char c) {
        if(Character.isUpperCase(c)) {
            c = Character.toLowerCase(c);
        } else {
            c = Character.toUpperCase(c);
        }
        return c;
    }
//使用ASCII码计算，效率会高一点
    char swapCase2(char c) {
        if(c >= 'A' && c <= 'Z') {
            c = (char) (c - 'A' + 'a');
        } else {
            c = (char) (c - 'a' + 'A');
        }
        return c;
    }

思路1：split+倒序遍历

split分割之后，倒序遍历数组

public class Solution {
    public String ReverseSentence(String str) {
        String[] arr = str.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = arr.length - 1; i >= 0; i--) {
            sb.append(arr[i]);
            if(i != 0) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

思路2：使用栈存储字符

不借助split函数，从末尾遍历将每个字符入栈，遇到空格时全部弹出

public class Solution {
    public String ReverseSentence(String str) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        //从末尾遍历
        for(int i = str.length() - 1; i >= 0; i--) {
            char c = str.charAt(i);
            //使用栈保存每个字符
            if(c != ' ') {
                stack.push(c);
            } else {
                //遇到空格时全部弹出，并补上空格
                while(!stack.isEmpty()) {
                    sb.append(stack.pop());
                }
                sb.append(' ');
            }
        }
        //最后一个单词，不用补空格
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}

思路3：使用栈存储单词

顺序遍历，拼接字符串，遇到空格，将字符串入栈，最后出栈拼接

示例：Stack={"I", "am", "a"}，最后一个单词已经在StringBuilder中了，不需要入栈

public class Solution {
    public String ReverseSentence(String str) {
        Stack<String> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(c != ' ') {
                sb.append(c);
            } else {
                stack.push(sb.toString());
                //将字符串清空
                sb.replace(0, sb.length(), "");
            }
        }
        //最后一个单词已经在StringBuilder中了，不需要入栈
        while(!stack.isEmpty()) {
            sb.append(" ");
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}

思路4：双指针

从末尾开始遍历，i指向单词头，j指向单词尾，遇到空格则切割单词

public class Solution {
    public String ReverseSentence(String str) {
        if(str.isEmpty()) {
            return "";
        }
        int i = str.length() - 1;
        //substring的end不包含，因此需要加1
        int j = i + 1;
        StringBuilder sb = new StringBuilder();
        //从后往前遍历
        while(i > 0) {
            char c = str.charAt(i);
            if(c == ' ') {
                //遇到空格，则切割单词
                //i+1跳过单词前的空格
                String s = str.substring(i + 1, j);
                sb.append(s);
                //在单词后面补上空格
                sb.append(' ');
                //j移到空格的位置
                j = i;
            }
            i--;
        }
        //最后一个单词没有空格，直接切割
        sb.append(str.substring(i, j));
        return sb.toString();
    }
}