Problem Statement in English

You are given a string s, which may contain leading or trailing spaces and multiple spaces between words.

Your task is to reverse the order of the words in the string while ensuring that there is only a single space separating the words in the final output, and no leading or trailing spaces.

Approach

To solve the problem of reversing the words in a string while handling extra spaces, we can follow these steps:

  • Split the string into words using the default whitespace delimiter, which automatically handles multiple spaces and trims leading/trailing spaces.
  • Reverse the list of words obtained from the split operation.
  • Join the reversed list of words back into a single string with a single space separating each word

Done.

Solution in Python


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

Complexity

  • Time: $O(n)$
    We traverse the string once to split it into words and then again to join them back together.

  • Space: $O(n)$
    Since we are storing all the words in a list before joining them back together.

And we are done.