题⽬描述

给定⼀个句⼦，将句⼦中的单词进⾏翻转，注意，单词内部的字符顺序不改变，改变的是单词与单词之间的顺序，⽐如“ I am a coder. ”,翻转之后变成“ coder. a am I ”。

示例
注意：引号内部才是输⼊的内容
输⼊："You are a cool boy."
输出："boy. cool a are You"

思路及解答

Java内置函数分割反转

Java ⾥⾯有切割字符串的⽅法，直接⽤空格进⾏分隔，分隔成为多个单词，然后从字符串数组的后⾯开始，每⼀个字符拼接上⼀个空格，但是，值得注意的⼀点是，当只剩下⼀个字符串的时候，也就是索引为 0 的时候，不需要再拼接空格。代码实现如下：

public class Solution {
    public String ReverseSentence(String str) {
        if (str == null || str.length() == 0 || str.equals(" ")) {
	        return "";
        }
        
        //去除首尾空格后，按照空格分隔
        String[] strs = str.trim().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) {
            stringBuilder.append(strs[i]);
            stringBuilder.append(i == 0 ? "" : " ");
        }
        return stringBuilder.toString();
    }
}

• 时间复杂度：O(n)，分割和拼接各需线性时间
• 空间复杂度：O(n)，存储单词数组和结果字符串

借助栈

借助栈，栈是先进后出，也就是我们切割完字符串之后，全部放到栈中，再全部取出来拼接，就可以完成逆序的操作。有⼀个值得注意的点，就是空格的问题，我们压栈的时候，跟随着拼接上空格即可，最后⼀个字符不压⼊空格。

public String ReverseSentence(String str) {
    if (str == null || str.length() == 0)
        return str;
    StringBuilder stringBuilder = new StringBuilder();
    String[] strs = str.split(" ");
    if (strs.length == 0)
        return str;
    Stack  stack = new Stack  ();
    for (int i = 0; i 

双指针法(推荐)

⾸先判断字符串 str 是否为空或者为空字符，如果 str 不为空，则初始化 start ，和 end 指针指向字符串的尾部， start 从尾部向头部遍历

针对每⼀个字符，如果字符为空字符：

• 如果 start 和 end 不是出于同⼀个位置，说明已经遍历完⼀个单词，那么将 start+1 ~ end 之间的字符，拼接到结果后，并且添加上⼀个空格。将 start-1 ，并且 end 指向 start 的位置
• 否则，说明是多余的空格，直接跳过， start-1 ， end=start

如果字符不是空字符：可以把 start 索引前移，也就是 start--

最后，剩下最后⼀个单词的时候，需要特殊处理最后⼀个单词，拼接到字符串后⾯就可以了。

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.ReverseSentence("nowcoder. a am I"));
    }
    public String ReverseSentence(String str) {
        if (str != null && str.length() != 0 && !str.equals(" ")) {
            int start = str.length() - 1, end = start;
            StringBuffer stringBuffer = new StringBuffer();
            for (; start > 0;) {
                // 如果为空格
                if (str.charAt(start) == ' ') {
                    // 且开始索引和结束索引不⼀致的情况
                    if (start != end) {
                        // 遍历start+1~end的字符，加到
                        for (int i = start + 1; i 

• 时间复杂度：O(n)，每个字符被访问常数次
• 空间复杂度：O(n)，StringBuilder存储结果

三次反转法（空间最优）

通过字符级操作实现O(1)空间复杂度（假设字符数组可修改）。

先反转整个字符串，再逐个反转每个单词

三次反转的数学原理：

对于句子 "A B C"（A、B、C为单词）：

1. 整体反转： "C' B' A'"
2. 单词反转： "C'"反转→ "C", "B'"反转→ "B", "A'"反转→ "A"
3. 结果： "C B A" → 正是期望的顺序

public class Solution {

    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return "";
        
        char[] chars = s.toCharArray();
        int n = chars.length;
        
        // 步骤1：反转整个字符串
        reverse(chars, 0, n - 1);
        
        // 步骤2：反转每个单词
        reverseWords(chars, n);
        
        // 步骤3：清理多余空格
        return cleanSpaces(chars, n);
    }
    
    /**
     * 反转字符数组的指定区间
     */
    private void reverse(char[] chars, int left, int right) {
        while (left 

• 时间复杂度：O(n)，三次线性遍历
• 空间复杂度：O(1)（如可修改原数组）或 O(n)（需创建新数组）

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top