LeetCode 第186题：反转字符串中的单词 II

题目描述

给你一个字符数组 s，反转该数组中单词的顺序。

单词的定义是：连续的非空格字符，单词的前后用空格字符隔开。单词中可能包含前导或尾随空格。

请你反转单词的顺序，但不要反转单词内字符的顺序。返回反转后的数组。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1:

输入：s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

示例 2:

输入：s = ["a"]
输出：["a"]

提示

• 1 <= s.length <= 10^5
• s[i] 可以是英文大小写字母、数字、空格 ' '、或者其他可见字符
• s 中至少存在一个单词
• s 不含前导或尾随空格
• 所有单词都被空格分隔

解题思路

方法：先整体反转，再逐个单词反转

这道题与 LeetCode 151 “反转字符串中的单词” 类似，但要求直接在原数组上操作。解决方法是：先将整个字符数组反转，然后再逐个反转每个单词。

关键点：

1. 将整个字符数组 s 反转
2. 遍历反转后的数组，对每个单词（连续的非空格字符）单独进行反转
3. 由于要求原地修改数组，我们需要使用双指针技巧来实现反转操作

时间复杂度：O(n)，其中 n 是字符数组的长度，我们只需要遍历数组常数次 空间复杂度：O(1)，只需要常数额外空间

代码实现

C# 实现

public class Solution {
    public void ReverseWords(char[] s) {
        // 1. 反转整个字符数组
        Reverse(s, 0, s.Length - 1);
        
        // 2. 反转每个单词
        int start = 0;
        for (int end = 0; end < s.Length; end++) {
            if (s[end] == ' ') {
                Reverse(s, start, end - 1);
                start = end + 1;
            }
        }
        
        // 反转最后一个单词（最后没有空格）
        Reverse(s, start, s.Length - 1);
    }
    
    private void Reverse(char[] s, int start, int end) {
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }
}

Python 实现

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 1. 反转整个字符数组
        self.reverse(s, 0, len(s) - 1)
        
        # 2. 反转每个单词
        start = 0
        for end in range(len(s)):
            if s[end] == ' ':
                self.reverse(s, start, end - 1)
                start = end + 1
        
        # 反转最后一个单词（最后没有空格）
        self.reverse(s, start, len(s) - 1)
    
    def reverse(self, s: List[str], start: int, end: int) -> None:
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

C++ 实现

class Solution {
public:
    void reverseWords(vector<char>& s) {
        // 1. 反转整个字符数组
        reverse(s.begin(), s.end());
        
        // 2. 反转每个单词
        int n = s.size();
        int start = 0;
        for (int end = 0; end < n; end++) {
            if (s[end] == ' ') {
                reverse(s.begin() + start, s.begin() + end);
                start = end + 1;
            }
        }
        
        // 反转最后一个单词（最后没有空格）
        reverse(s.begin() + start, s.end());
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	296 ms	44.2 MB	使用自定义的反转函数
Python	180 ms	18.9 MB	利用Python的交换语法，简洁高效
C++	16 ms	15.6 MB	使用标准库reverse函数，性能最优

补充说明

代码亮点

1. 使用“先整体反转，再逐个单词反转”的两步法，算法简洁高效
2. 利用双指针技巧实现原地反转，不需要额外空间
3. C++实现中利用了标准库的reverse函数，简化了代码

为什么这种方法有效？

这种方法的巧妙之处在于利用了反转操作的性质：

• 如果我们将整个字符串反转，单词的顺序会反转，但每个单词内部的字符也会反转
• 然后，我们再单独反转每个单词，这样单词内部的字符顺序又恢复正常了
• 最终结果是：单词的顺序反转了，但单词内部的字符顺序保持不变

常见错误

1. 忘记处理最后一个单词（最后一个单词后面没有空格）
2. 反转单词的边界处理不当，导致单词反转不正确
3. 对于单个字符或空数组的边界情况处理不当

相关题目

• 151. 反转字符串中的单词
• 344. 反转字符串
• 557. 反转字符串中的单词 III