# 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:

```python
s = "  hello world  "
```

The words are:

```python
["hello", "world"]
```

After reversing the order:

```python
["world", "hello"]
```

So the answer is:

```python
"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

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | A string with the words in reverse order |
| Word definition | A sequence of non-space characters |
| Space rule | Output has one space between words |
| Extra spaces | Removed from the output |

Example function shape:

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

## Examples

Example 1:

```python
s = "the sky is blue"
```

The words are:

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

Reverse their order:

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

Output:

```python
"blue is sky the"
```

Example 2:

```python
s = "  hello world  "
```

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

Output:

```python
"world hello"
```

Example 3:

```python
s = "a good   example"
```

There are three spaces between `good` and `example`.

The output must reduce them to one space.

Output:

```python
"example good a"
```

## First Thought: Split, Reverse, Join

Python already gives us a useful method:

```python
s.split()
```

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

For example:

```python
"  a good   example  ".split()
```

gives:

```python
["a", "good", "example"]
```

Then we reverse the list:

```python
["example", "good", "a"]
```

Finally, we join the words with one space:

```python
"example good a"
```

## Algorithm

The algorithm has three steps.

First, split the string into words:

```python
words = s.split()
```

Second, reverse the word list:

```python
words.reverse()
```

Third, join the words with a single space:

```python
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:

```python
"blue is sky the"
```

not:

```python
"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`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the string to split it, reverse the words, and join them |
| Space | `O(n)` | We store the extracted words and the returned string |

## Implementation

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

## Code Explanation

This line extracts the words:

```python
words = s.split()
```

It handles all spacing cases for us.

For example:

```python
"  hello   world  ".split()
```

becomes:

```python
["hello", "world"]
```

This line reverses the list in place:

```python
words.reverse()
```

So:

```python
["hello", "world"]
```

becomes:

```python
["world", "hello"]
```

This line builds the final string:

```python
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.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `"the sky is blue"` | Basic word reversal |
| `"  hello world  "` | Removes leading and trailing spaces |
| `"a good   example"` | Reduces multiple spaces |
| `"single"` | Handles one word |
| `"  many   spaces   here  "` | Combines all spacing issues |
| `"123 abc DEF"` | Handles digits and mixed case |