Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

186. Reverse Words in a String II

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  void reverseWords(vector<char>& s) {
    reverse(begin(s), end(s));  // 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 spaces
        ++i;
      while (j < i || j < n && s[j] != ' ')  // Skip non spaces
        ++j;
      reverse(begin(s) + i, begin(s) + j);  // Reverse the word
    }
  }
};




			


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 spaces
        ++i;
      while (j < i || j < n && s[j] != ' ') // Skip non spaces
        ++j;
      reverse(s, i, j - 1); // Reverse the word
    }
  }
}




			


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 spaces
          i += 1
        while j < i or (j < n and s[j] != ' '):  # Skip non 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