Reverse Words in a String LeetCode Solution | Easy Approach

Reverse Words in a String Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

• 1 <= s.length <= 104
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

Reverse Words in a String Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  string reverseWords(string s) {
    reverse(begin(s), end(s));          // reverse the whole string
    reverseWords(s, s.length());        // reverse each word
    return cleanSpaces(s, s.length());  // clean up 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 spaces
        ++i;
      while (j < i || j < n && s[j] != ' ')  // skip non spaces
        ++j;
      reverse(begin(s) + i, begin(s) + 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 spaces
        ++j;
      while (j < n && s[j] != ' ')  // keep non spaces
        s[i++] = s[j++];
      while (j < n && s[j] == ' ')  // skip spaces
        ++j;
      if (j < n)  // keep only one space
        s[i++] = ' ';
    }

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

Java

 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 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 spaces
        ++i;
      while (j < i || j < n && sb.charAt(j) != ' ') // skip non 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 spaces
        ++j;
      while (j < n && sb.charAt(j) != ' ') // keep non spaces
        sb.setCharAt(i++, sb.charAt(j++));
      while (j < n && sb.charAt(j) == ' ') // skip 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);
    }
  }
}

Python

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

Watch Tutorial

Checkout more Solutions here