151. Reverse Words in a String

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string reverseWords(string s) {
    ranges::reverse(s);                 // Reverse the whole string.
    reverseWords(s, s.length());        // Reverse each word.
    return cleanSpaces(s, s.length());  // Clean up the spaces.
  }

 private:
  void reverseWords(string& 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.
    }
  }

  // Trim leading, trailing, and middle spaces
  string cleanSpaces(string& s, int n) {
    int i = 0;
    int j = 0;

    while (j < n) {
      while (j < n && s[j] == ' ')  // Skip the spaces.
        ++j;
      while (j < n && s[j] != ' ')  // Keep non spaces
        s[i++] = s[j++];
      while (j < n && s[j] == ' ')  // Skip the spaces.
        ++j;
      if (j < n)  // Keep only one space.
        s[i++] = ' ';
    }

    return s.substr(0, i);
  }
};

class Solution {
  public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder(s).reverse(); // Reverse the whole string.
    reverseWords(sb, sb.length());                     // Reverse each word.
    return cleanSpaces(sb, sb.length());               // Clean up the spaces.
  }

  private void reverseWords(StringBuilder sb, int n) {
    int i = 0;
    int j = 0;

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

  // Trim leading, trailing, and middle spaces
  private String cleanSpaces(StringBuilder sb, int n) {
    int i = 0;
    int j = 0;

    while (j < n) {
      while (j < n && sb.charAt(j) == ' ') // Skip the spaces.
        ++j;
      while (j < n && sb.charAt(j) != ' ') // Keep non spaces
        sb.setCharAt(i++, sb.charAt(j++));
      while (j < n && sb.charAt(j) == ' ') // Skip the spaces.
        ++j;
      if (j < n) // Keep only one space.
        sb.setCharAt(i++, ' ');
    }

    return sb.substring(0, i).toString();
  }

  private void reverse(StringBuilder sb, int l, int r) {
    while (l < r) {
      final char temp = sb.charAt(l);
      sb.setCharAt(l++, sb.charAt(r));
      sb.setCharAt(r--, temp);
    }
  }
}

class Solution:
  def reverseWords(self, s: str) -> str:
    return ' '.join(reversed(s.split()))