Skip to content

186. Reverse Words in a String II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  void reverseWords(vector<char>& s) {
    reverse(s.begin(), s.end());  // Reverse the whole string.
    reverseWords(s, s.size());    // Reverse each word.
  }

 private:
  void reverseWords(vector<char>& s, int n) {
    int i = 0;
    int j = 0;

    while (i < n) {
      while (i < j || i < n && s[i] == ' ')  // Skip the spaces.
        ++i;
      while (j < i || j < n && s[j] != ' ')  // Skip the spaces.
        ++j;
      reverse(s.begin() + i, s.begin() + j);  // Reverse the word.
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public void reverseWords(char[] s) {
    reverse(s, 0, s.length - 1); // Reverse the whole string.
    reverseWords(s, s.length);   // Reverse each word.
  }

  private void reverse(char[] s, int l, int r) {
    while (l < r) {
      final char c = s[l];
      s[l++] = s[r];
      s[r--] = c;
    }
  }

  private void reverseWords(char[] s, int n) {
    int i = 0;
    int j = 0;

    while (i < n) {
      while (i < j || i < n && s[i] == ' ') // Skip the spaces.
        ++i;
      while (j < i || j < n && s[j] != ' ') // Skip the spaces.
        ++j;
      reverse(s, i, j - 1); // Reverse the word.
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def reverseWords(self, s: List[str]) -> None:
    def reverse(l: int, r: int) -> None:
      while l < r:
        s[l], s[r] = s[r], s[l]
        l += 1
        r -= 1

    def reverseWords(n: int) -> None:
      i = 0
      j = 0

      while i < n:
        while i < j or (i < n and s[i] == ' '):  # Skip the spaces.
          i += 1
        while j < i or (j < n and s[j] != ' '):  # Skip the spaces.
          j += 1
        reverse(i, j - 1)  # Reverse the word.

    reverse(0, len(s) - 1)  # Reverse the whole string.
    reverseWords(len(s))  # Reverse each word.