題⽬描述

給定⼀個句⼦，將句⼦中的單詞進⾏翻轉，注意，單詞內部的字符順序不改變，改變的是單詞與單詞之間的順序，⽐如“ 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 < String > stack = new Stack < > ();
    for (int i = 0; i < strs.length - 1; i++) {
        stack.push(strs[i]);
        stack.push(" ");
    }
    stack.push(strs[strs.length - 1]);
    while (!stack.isEmpty()) {
        stringBuilder.append(stack.pop());
    }
    return stringBuilder.toString();
}

雙指針法(推薦)

⾸先判斷字符串 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 <= end; i++) {
                            stringBuffer.append(str.charAt(i));
                        }
                        // 每⼀個單詞的後⾯加上⼀個空格
                        stringBuffer.append(" ");
                    }
                    start--;
                    end = start;
                } else {
                    start--;
                }
            }
            // 處理最後⼀個單詞
            for (int i = 0; i <= end; i++) {
                stringBuffer.append(str.charAt(i));
            }
            return stringBuffer.toString();
        }
        return str;
    }
}

• 時間複雜度：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 < right) {
            char temp = chars[left];
            chars[left++] = chars[right];
            chars[right--] = temp;
        }
    }
    
    /**
     * 反轉每個單詞
     */
    private void reverseWords(char[] chars, int n) {
        int i = 0, j = 0;
        
        while (i < n) {
            // 跳過前導空格
            while (i < j || (i < n && chars[i] == ' ')) i++;
            // 找到單詞結尾
            while (j < i || (j < n && chars[j] != ' ')) j++;
            // 反轉單詞
            reverse(chars, i, j - 1);
        }
    }
    
    /**
     * 清理多餘空格，返回最終字符串
     */
    private String cleanSpaces(char[] chars, int n) {
        int i = 0, j = 0;
        
        while (j < n) {
            // 跳過前導空格
            while (j < n && chars[j] == ' ') j++;
            // 保留單詞間的一個空格
            while (j < n && chars[j] != ' ') {
                chars[i++] = chars[j++];
            }
            // 添加單詞間空格
            while (j < n && chars[j] == ' ') j++;
            if (j < n) {
                chars[i++] = ' ';
            }
        }
        
        return new String(chars, 0, i);
    }
}

• 時間複雜度：O(n)，三次線性遍歷
• 空間複雜度：O(1)（如可修改原數組）或 O(n)（需創建新數組）