LeetCode 151: Reverse Words in a String Solution in Python Explained

Problem Statement

In LeetCode 151, you’re given a string s containing words separated by spaces. Your task is to reverse the order of the words, ensuring no leading or trailing spaces and exactly one space between words, returning the result as a string. This differs from expression evaluation like LeetCode 150: Evaluate Reverse Polish Notation, focusing on string manipulation rather than arithmetic.

Constraints

• 1 <= s.length <= 10^4
• s contains English letters, digits, and spaces
• At least one word in s
• No leading or trailing spaces in examples, but solution must handle them

Example

Let’s see some cases:

Copy codeInput: s = "the sky is blue"
Output: "blue is sky the"
Explanation: Words reversed, single spaces between.

Copy codeInput: s = "  hello world  "
Output: "world hello"
Explanation: Extra spaces removed, words reversed.

Copy codeInput: s = "a good   example"
Output: "example good a"
Explanation: Multiple spaces between words reduced to one.

These examples show we’re reversing word order and cleaning spaces.

Understanding the Problem

How do you solve LeetCode 151: Reverse Words in a String in Python? Take s = "the sky is blue". We need "blue is sky the"—reverse the word order (the→blue, sky→is, etc.) and ensure single spaces. For " hello world ", remove extra spaces to get "world hello". This isn’t a list sorting task like LeetCode 148: Sort List; it’s about string word reversal. We’ll use: 1. Two-Pointer In-Place Reversal: O(n) time, O(1) space—our best solution. 2. String Split and Join: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two-Pointer In-Place Reversal Approach

Explanation

Two-Pointer In-Place Reversal processes the string in three steps using O(1) space: 1. Reverse Entire String: Flip all characters. 2. Reverse Each Word: Identify word boundaries and reverse them. 3. Clean Spaces: Remove extra spaces in-place, ensuring single spaces between words.

This is the best solution due to its O(n) time complexity, O(1) space usage (modifying the string as a list in-place), and efficiency without extra allocations, aligning with the problem’s potential space constraint focus.

For "the sky is blue":

• Reverse all: "eulb si yks eht".
• Reverse words: "blue is sky the".
• Clean spaces: "blue is sky the".

Step-by-Step Example

Example 1: s = "the sky is blue"

Goal: Return "blue is sky the".

• Step 1: Convert to list, s = ['t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e'].
• Step 2: Reverse entire string.
• s = ['e','u','l','b',' ','s','i',' ','y','k','s',' ','e','h','t'].
• Step 3: Reverse each word.
• Word 0-3: "eulb" → "blue", s = ['b','l','u','e',' ','s','i',' ','y','k','s',' ','e','h','t'].
• Word 5-6: "si" → "is", s = ['b','l','u','e',' ','i','s',' ','y','k','s',' ','e','h','t'].
• Word 8-10: "yks" → "sky", s = ['b','l','u','e',' ','i','s',' ','s','k','y',' ','e','h','t'].
• Word 12-14: "eht" → "the", s = ['b','l','u','e',' ','i','s',' ','s','k','y',' ','t','h','e'].
• Step 4: Clean spaces (already clean), join: "blue is sky the".
• Finish: Return "blue is sky the".

Example 2: s = " hello world "

Goal: Return "world hello".

• Step 1: s = [' ',' ','h','e','l','l','o',' ','w','o','r','l','d',' ',' '].
• Step 2: Reverse: s = [' ',' ','d','l','r','o','w',' ','o','l','l','e','h',' ',' '].
• Step 3: Reverse words:
• "dlrow" → "world", "olleh" → "hello".
• s = [' ',' ','w','o','r','l','d',' ','h','e','l','l','o',' ',' '].
• Step 4: Clean spaces: s = ['w','o','r','l','d',' ','h','e','l','l','o'], join: "world hello".
• Finish: Return "world hello".

Example 3: s = "a good example"

Goal: Return "example good a".

• Step 1: s = ['a',' ','g','o','o','d',' ',' ',' ','e','x','a','m','p','l','e'].
• Step 2: Reverse: s = ['e','l','p','m','a','x','e',' ',' ',' ','d','o','o','g',' ','a'].
• Step 3: Reverse words:
• "elpmaxe" → "example", "doog" → "good", "a" → "a".
• s = ['e','x','a','m','p','l','e',' ',' ',' ','g','o','o','d',' ','a'].
• Step 4: Clean spaces: s = ['e','x','a','m','p','l','e',' ','g','o','o','d',' ','a'], join: "example good a".
• Finish: Return "example good a".

How the Code Works (Two-Pointer In-Place Reversal) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef reverseWords(s: str) -> str:
    # Line 1: Convert string to list for in-place modification
    s = list(s)
    # e.g., ['t','h','e',' ','s','k','y','...]
    n = len(s)
    # Length (e.g., 15)

    # Line 2: Reverse entire string
    def reverse(start: int, end: int):
        # Helper to reverse s[start:end+1]
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1
    reverse(0, n-1)
    # e.g., ['e','u','l','b',' ','s','i','...]

    # Line 3: Reverse each word
    start = 0
    # Start of current word (e.g., 0)
    end = 0
    # End of current word (e.g., 0)
    while end < n:
        # Process all characters (e.g., 0 to 14)
        while start < n and s[start] == ' ':
            # Skip leading spaces (e.g., initial spaces)
            start += 1
        end = start
        # Move end to start (e.g., 0)
        while end < n and s[end] != ' ':
            # Find word end (e.g., 3 for "blue")
            end += 1
        if start < n:
            # If word exists (e.g., 0 < 15)
            reverse(start, end-1)
            # Reverse word (e.g., "eulb"→"blue")
            start = end
            # Move to next word (e.g., 4)

    # Line 4: Clean spaces in-place
    write = 0
    # Write position (e.g., 0)
    read = 0
    # Read position (e.g., 0)
    while read < n:
        # Process all characters (e.g., 0 to 14)
        while read < n and s[read] == ' ':
            # Skip leading spaces (e.g., initial spaces)
            read += 1
        if read == n:
            # If only spaces left, break
            break
        if write > 0:
            # Add space before next word (e.g., after "blue")
            s[write] = ' '
            write += 1
        while read < n and s[read] != ' ':
            # Copy word (e.g., "blue")
            s[write] = s[read]
            write += 1
            read += 1

    # Line 5: Return result as string
    return ''.join(s[:write])
    # Join up to write position (e.g., "blue is sky the")

This detailed breakdown clarifies how two-pointer in-place reversal efficiently reverses words.

Alternative: String Split and Join Approach

Explanation

String Split and Join splits the string into words, reverses the list, and joins with single spaces. It’s a practical alternative, simple with O(n) time, but uses O(n) space for the word list, less efficient than in-place for space constraints.

For "the sky is blue":

• Split: ["the", "sky", "is", "blue"].
• Reverse: ["blue", "is", "sky", "the"].
• Join: "blue is sky the".

Step-by-Step Example (Alternative)

For " hello world ":

• Step 1: split() = ["hello", "world"].
• Step 2: Reverse: ["world", "hello"].
• Step 3: Join: "world hello".
• Finish: Return "world hello".

How the Code Works (Split and Join)

Copy codedef reverseWordsSplit(s: str) -> str:
    words = s.split()
    words.reverse()
    return ' '.join(words)

Complexity

• Two-Pointer In-Place Reversal:
• Time: O(n) – single pass for reversal and cleaning.
• Space: O(1) – modifies list in-place (input conversion aside).
• String Split and Join:
• Time: O(n) – split, reverse, join operations.
• Space: O(n) – word list storage.

Efficiency Notes

Two-Pointer In-Place Reversal is the best solution with O(n) time and O(1) space (excluding initial list conversion), offering efficiency and minimal memory use—String Split and Join matches time complexity but uses O(n) space, making it simpler but less space-efficient.

Key Insights

• In-Place: Saves space.
• Split/Join: Quick and readable.
• Spaces: Must be cleaned.

Additional Example

For s = "Python is fun":

• Goal: "fun is Python".
• In-Place: Reverse "nuf si nohtyP", then "fun is Python".

Edge Cases

• Single Word: "hello" → "hello".
• Multiple Spaces: " a b " → "b a".
• Empty String: " " → "".

Both solutions handle these well.

Final Thoughts

LeetCode 151: Reverse Words in a String in Python is a fun string manipulation challenge. The Two-Pointer In-Place Reversal solution excels with its space efficiency and clarity, while String Split and Join offers a quick alternative. Want more? Try LeetCode 150: Evaluate Reverse Polish Notation for expression evaluation or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 151 on LeetCode with "the sky is blue", aiming for "blue is sky the"—test your skills now!