LeetCode 151: Reverse Words in a String

Problem Restatement

We are given a string s.

The string contains words separated by spaces. A word is a sequence of non-space characters.

We need to return a new string where the words appear in reverse order.

The output must follow two rules:

1. Words are separated by exactly one space.
2. There are no leading or trailing spaces.

For example:

s = "  hello world  "

The words are:

["hello", "world"]

After reversing the order:

["world", "hello"]

So the answer is:

"world hello"

LeetCode also states that s.length is between 1 and 10^4, the string contains English letters, digits, and spaces, and there is at least one word in s.

Input and Output

Example function shape:

def reverseWords(s: str) -> str:
    ...

Examples

Example 1:

s = "the sky is blue"

The words are:

["the", "sky", "is", "blue"]

Reverse their order:

["blue", "is", "sky", "the"]

Output:

"blue is sky the"

Example 2:

s = "  hello world  "

The leading and trailing spaces do not appear in the answer.

Output:

"world hello"

Example 3:

s = "a good   example"

There are three spaces between good and example.

The output must reduce them to one space.

Output:

"example good a"

First Thought: Split, Reverse, Join

Python already gives us a useful method:

s.split()

When called without arguments, split() separates the string by whitespace and ignores repeated spaces.

For example:

"  a good   example  ".split()

gives:

["a", "good", "example"]

Then we reverse the list:

["example", "good", "a"]

Finally, we join the words with one space:

"example good a"

Algorithm

The algorithm has three steps.

First, split the string into words:

words = s.split()

Second, reverse the word list:

words.reverse()

Third, join the words with a single space:

return " ".join(words)

This works because split() removes the extra spacing problem before we reverse anything.

The problem asks us to reverse words, not characters.

So "the sky is blue" becomes:

"blue is sky the"

not:

"eulb si yks eht"

Correctness

After calling s.split(), the list words contains every word from s in its original left-to-right order.

Extra spaces do not become words, so leading spaces, trailing spaces, and repeated spaces between words are removed.

After reversing words, the last word from the original string becomes the first word in the result, the second-to-last word becomes the second word, and so on.

Joining with " ".join(words) places exactly one space between adjacent words.

Therefore, the returned string contains all original words in reverse order, with no leading spaces, no trailing spaces, and exactly one space between words.

This matches the required output.

Complexity

Let n be the length of s.

Implementation

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

Code Explanation

This line extracts the words:

words = s.split()

It handles all spacing cases for us.

For example:

"  hello   world  ".split()

becomes:

["hello", "world"]

This line reverses the list in place:

words.reverse()

So:

["hello", "world"]

becomes:

["world", "hello"]

This line builds the final string:

return " ".join(words)

It inserts exactly one space between words.

Manual Two-Pointer Version

Some interviews may ask for the parsing logic without depending on split().

We can scan the string manually and collect words.

class Solution:
    def reverseWords(self, s: str) -> str:
        words = []
        n = len(s)
        i = 0

        while i < n:
            while i < n and s[i] == " ":
                i += 1

            if i >= n:
                break

            j = i
            while j < n and s[j] != " ":
                j += 1

            words.append(s[i:j])
            i = j

        words.reverse()
        return " ".join(words)

This version does the same work explicitly.

i skips spaces.

j moves to the end of the current word.

Then s[i:j] extracts the word.

Testing

def run_tests():
    sol = Solution()

    assert sol.reverseWords("the sky is blue") == "blue is sky the"
    assert sol.reverseWords("  hello world  ") == "world hello"
    assert sol.reverseWords("a good   example") == "example good a"
    assert sol.reverseWords("single") == "single"
    assert sol.reverseWords("  many   spaces   here  ") == "here spaces many"
    assert sol.reverseWords("123 abc DEF") == "DEF abc 123"

    print("all tests passed")

run_tests()