Question

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

English Version

题目描述

给你一个字符数组 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 <= s.length <= 105
• s[i] 可以是一个英文字母（大写或小写）、数字、或是空格 ' ' 。
• s 中至少存在一个单词
• s 不含前导或尾随空格
• 题目数据保证：s 中的每个单词都由单个空格分隔

解法

方法一

class Solution:
  def reverseWords(self, s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """

    def reverse(s, i, j):
      while i < j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1

    i, j, n = 0, 0, len(s)
    while j < n:
      if s[j] == ' ':
        reverse(s, i, j - 1)
        i = j + 1
      elif j == n - 1:
        reverse(s, i, j)
      j += 1
    reverse(s, 0, n - 1)

class Solution {
  public void reverseWords(char[] s) {
    int n = s.length;
    for (int i = 0, j = 0; j < n; ++j) {
      if (s[j] == ' ') {
        reverse(s, i, j - 1);
        i = j + 1;
      } else if (j == n - 1) {
        reverse(s, i, j);
      }
    }
    reverse(s, 0, n - 1);
  }

  private void reverse(char[] s, int i, int j) {
    for (; i < j; ++i, --j) {
      char t = s[i];
      s[i] = s[j];
      s[j] = t;
    }
  }
}

class Solution {
public:
  void reverseWords(vector<char>& s) {
    int n = s.size();
    for (int i = 0, j = 0; j < n; ++j) {
      if (s[j] == ' ') {
        reverse(s, i, j - 1);
        i = j + 1;
      } else if (j == n - 1) {
        reverse(s, i, j);
      }
    }
    reverse(s, 0, n - 1);
  }

  void reverse(vector<char>& s, int i, int j) {
    for (; i < j; ++i, --j) {
      swap(s[i], s[j]);
    }
  }
};

func reverseWords(s []byte) {
  n := len(s)
  for i, j := 0, 0; j < n; j++ {
    if s[j] == ' ' {
      reverse(s, i, j-1)
      i = j + 1
    } else if j == n-1 {
      reverse(s, i, j)
    }
  }
  reverse(s, 0, n-1)
}

func reverse(s []byte, i, j int) {
  for i < j {
    s[i], s[j] = s[j], s[i]
    i++
    j--
  }
}