---

0186. 反转字符串中的单词 II

• 标签：双指针、字符串
• 难度：中等

题目链接

• 0186. 反转字符串中的单词 II - 力扣

题目大意

描述：

给定一个字符数组 $s$。

要求：

反转其中「单词」的顺序。

说明：

• 「单词」的定义为：单词是一个由非空格字符组成的序列。$s$ 中的单词将会由单个空格分隔。
• 必须设计并实现「原地」解法来解决此问题，即不分配额外的空间。
• $1 \le s.length \le 10^{5}$。
• $s[i]$ 可以是一个英文字母（大写或小写）、数字、或是空格 ' '。
• $s$ 中至少存在一个单词。
• $s$ 不含前导或尾随空格。
• 题目数据保证：$s$ 中的每个单词都由单个空格分隔。

示例：

• 示例 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：双指针 + 两次反转

这是一个典型的原地反转问题。我们可以使用「两次反转」的策略来解决：

1. 整体反转：先将整个字符数组 $s$ 反转。
2. 单词反转：然后逐个反转每个单词。

核心思想：

• 使用双指针 $left$ 和 $right$ 来标记单词的边界。
• 第一次反转：将整个数组 $s[0:n-1]$ 反转。
• 第二次反转：遍历数组，当遇到空格或到达末尾时，反转当前单词 $s[left:right]$。

算法步骤：

1. 整体反转：将 $s[0:n-1]$ 反转，其中 $n$ 是数组长度。
2. 单词反转：
   • 初始化 $left = 0$，遍历数组。
   • 当 $s[i]$ 是空格或到达末尾时，反转 $s[left:i]$。
   • 更新 $left = i + 1$ 继续下一个单词。

关键点：

• 使用双指针 $left$ 和 $right$ 标记单词边界。
• 两次反转策略：先整体反转，再逐个单词反转。
• 原地操作，不分配额外空间。

思路 1：代码

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        
        # 第一次反转：整体反转整个数组
        self.reverse(s, 0, n - 1)
        
        # 第二次反转：逐个反转每个单词
        left = 0
        for i in range(n + 1):  # 包含n是为了处理最后一个单词
            # 当遇到空格或到达末尾时，反转当前单词
            if i == n or s[i] == ' ':
                self.reverse(s, left, i - 1)
                left = i + 1  # 更新下一个单词的起始位置
    
    def reverse(self, s: List[str], left: int, right: int) -> None:
        """
        反转数组s中从left到right的部分
        """
        while left < right:
            # 交换左右指针位置的字符
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度。需要遍历数组两次：一次整体反转，一次逐个单词反转。
• 空间复杂度：$O(1)$，只使用了常数额外空间，满足原地操作的要求。