📃 题目描述

题目链接：557. 反转字符串中的单词 III - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

提示：

• 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格

🔔 解题思路

这个没啥好说的，以空格为界，使用双指针挨个反转单词即可。

一个指针指向单词的起始位置，另一个指向指向单词的结束位置。

class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0 || s.equals(" ")) {
            return s;
        }

        char[] arr = s.toCharArray();

        int start = 0;
        int end = 0;
        while (end < arr.length) {
            // 找到单词的结束位置（最后一个字符的位置）
            while (end < arr.length - 1 && arr[end + 1] != ' ') {
                end ++;
            }

            // 反转这个单词
            reverse(arr, start, end);

            // 继续寻找下一个单词
            end = end + 2;
            start = end;
        }

        // 注意这里不要用 Arrays.toString 和 arr.toS
        return new String(arr);
    }
    
    /**
     * 反转 arr[] 从 start 到 end 位置的字符
     */
    private static void reverse(char[] arr, int start, int end) {
        if (arr == null || arr.length == 0 || start == end || start > end) {
            return ;
        }

        while (start < end) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start ++;
            end --;
        }
    }
}

上述代码是把 end 作为每个单词的最后一位，end + 1 不断地往前试探空格

也可以把 end - 1 作为最后单词的最后一位，end 不断地往前试探空格

class Solution {
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();

        int start = 0;
        int end = 0;
        while (end < arr.length) {
            while (end < arr.length && arr[end] != ' ') {
                end ++;
            }
           
            reverse(arr, start, end - 1);
            end += 1;
            start = end;
        }
        
        // 反转最后一个单词
        reverse(arr, start, arr.length - 1);

        return new String(arr);
    }
}

💥 复杂度分析

• 空间复杂度：需要将 String 需要转成字符数组，O(N)
• 时间复杂度：O(N)，字符串中的每个字符要么在 O(1) 的时间内被交换到相应的位置，要么因为是空格而保持不动