Problem Definition

LeetCode link: 151. 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.

Thought Process

When approaching this problem, we first need to consider how to handle Python's string immutability. Unlike languages like C++ where strings can be modified in place, Python strings are immutable, which means any modification creates a new string. This fundamentally affects our approach to space complexity.

The next consideration is whether to use Python's built-in functions. While split() would make the problem trivial, understanding how to solve it without relying solely on built-ins helps us develop better problem-solving skills. We can explore multiple approaches, from using two pointers to implementing a stack-based solution.

Key Insights

The main challenge isn't just reversing the words - it's handling the spaces efficiently. Python's string methods like split() handle multiple spaces automatically, but understanding how to do this manually is valuable for similar problems. We can also leverage Python's list operations since they're more efficient for manipulation than strings.

Solution 1: A Three-Step Pythonic Solution

class Solution:
    def reverseWords(self, s: str) -> str:
        # Remove leading and trailing whitespace
        s = s.strip()
        # Reverse the entire string
        s = s[::-1]
        # Split into words, reverse each word, and join back together
        s = ' '.join(word[::-1] for word in s.split())
        return s

This is a clever three-step solution that utilizes Python's built-in string operations to reverse words. Let's break it down step by step:

  1. s = s.strip()
    • First, we remove any leading and trailing whitespace from the string
    • For example: " hello world " becomes "hello world"
  2. s = s[::-1]
    • This reverses the entire string using Python's slice notation with step -1
    • "hello world" becomes "dlrow olleh"
  3. s = ' '.join(word[::-1] for word in s.split())
    • s.split() breaks the string into a list of words, automatically handling multiple spaces
    • word[::-1] reverses each individual word
    • Generator expression (word[::-1] for word in s.split()) creates reversed words one at a time
    • ' '.join() combines the words back together with single spaces between them
    • "dlrow olleh" becomes "world hello"

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(n) due to creating new strings (strings are immutable in Python)

The beauty of this solution lies in its conciseness while still handling all edge cases:

  • Multiple spaces between words (handled by split())
  • Leading and trailing spaces (handled by strip())
  • Preserving word order while reversing (handled by the two-stage reversal)

It's a great example of utilizing Python's built-in string manipulation features effectively. However, it's worth noting that while this solution is very Pythonic and readable, it may use more memory than necessary since each operation creates a new string.

Solution 2: Two-Pointer Technique

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        left, right = 0, len(words) - 1
        
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1
            
        return " ".join(words)

The two-pointer technique is a fundamental algorithm pattern. Here's how it works:

  1. First, we use split() which automatically handles all types of spaces (leading, trailing, multiple spaces between words)
  2. We set up two pointers: left starting at the beginning and right at the end
  3. We swap words at these positions and move the pointers inward until they meet
  4. Finally, we join the words back together with single spaces

Time Complexity: O(n) where n is the string length.

Space Complexity: O(n) to store the words list

Solution 3: Pythonic String Slicing

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

This solution showcases Python's expressive power. Let's break down what's happening:

  1. s.split() creates a list of words, automatically handling all spacing issues
  2. [::-1] is Python's slice notation where -1 step means reverse the sequence
  3. " ".join() combines the words with single spaces between them

While this solution looks simple, it's actually performing several operations:

  • Splitting the string into a list of words - O(n)
  • Creating a reversed copy of the list - O(n)
  • Joining the words back together - O(n)

Time Complexity: O(n)

Space Complexity: O(n)

Solution 4: Character-by-Character Processing

class Solution:
    def reverseWords(self, s: str) -> str:
        words = []
        current_word = []
        
        for char in s:
            if char != ' ':
                current_word.append(char)
            elif current_word:
                words.append(''.join(current_word))
                current_word = []
        
        # Handle the last word if it exists
        if current_word:
            words.append(''.join(current_word))
        
        return ' '.join(reversed(words))

This solution provides the most detailed control over the process:

  1. We iterate through each character in the string
  2. When we find a non-space character, we add it to the current_word list
  3. When we encounter a space and have a current word, we join that word and add it to our words list
  4. We have special handling for the last word (which might not be followed by a space)
  5. Finally, we reverse the word list and join with spaces

This approach is particularly useful when you need to modify the word collection process, such as adding filters or transformations to the words.

Time Complexity: O(n) where n is the length of the string

Space Complexity: O(n) to store the characters and words

The key advantages of this approach:

  1. Explicit control over word building
  2. Automatically handles multiple spaces (they're skipped)
  3. No dependence on Python's built-in split() function
  4. Clear understanding of how words are formed and stored

Solution 5: Using Built-in Methods Efficiently

class Solution:
    def reverseWords(self, s: str) -> str:
        # Remove leading/trailing spaces and normalize spaces between words
        normalized = ' '.join(s.split())
        
        # Convert to list for character manipulation
        chars = list(normalized)
        
        # Reverse the entire string
        chars.reverse()
        
        # Helper function to reverse portion of list
        def reverse_range(arr, start, end):
            while start < end:
                arr[start], arr[end] = arr[end], arr[start]
                start += 1
                end -= 1
        
        # Reverse each word
        start = 0
        for end in range(len(chars) + 1):
            if end == len(chars) or chars[end] == ' ':
                reverse_range(chars, start, end - 1)
                start = end + 1
        
        return ''.join(chars)

This solution combines built-in methods with manual processing:

  1. First uses split() and join() to normalize spaces
  2. Converts to a character list for manipulation
  3. Reverses the entire string
  4. Then reverses each word individually
  5. Uses a helper function for range reversal

This approach shows how to combine Python's built-in efficiency with custom processing when needed.

Time Complexity: O(n), where n is the length of the input string

Space Complexity: O(n)

Difference between strip() and split()

strip()

  • Removes leading and trailing whitespace (or specified characters) from a string
  • Works only at the beginning and end of the string
  • Does NOT affect spaces between words
  • Returns a new string

split()

  • Breaks a string into a list of substrings
  • By default, splits on whitespace (any whitespace character, including spaces, tabs, newlines)
  • Removes all whitespace between words by default
  • Returns a list of strings

Key differences:

  1. Output type:
    • strip() returns a string
    • split() returns a list
  2. Scope of operation:
    • strip() only affects the start and end
    • split() affects the entire string
  3. Handling of internal spaces:
    • strip() preserves internal spaces
    • split() removes all extra whitespace between words

This is why in string processing, they're often used together:

s = "   hello    world   "
words = s.strip().split()  # First remove outer spaces, then split into words
print(words)  # Output: ['hello', 'world']

Key Takeaways

  1. There are multiple approaches to reverse words in a string, ranging from Pythonic one-liners to detailed character-by-character processing.
  2. Understanding string immutability in Python is crucial for space complexity considerations - any string modification creates a new string.
  3. Built-in functions like strip() and split() offer efficient solutions, but knowing how to implement manual solutions provides deeper algorithmic understanding.
  4. All solutions maintain O(n) time complexity, but they differ in code readability, memory usage, and implementation complexity.
  5. The two-pointer technique and stack-based approaches demonstrate fundamental computer science concepts while solving this problem.
  6. String manipulation in Python often requires conversion between strings and lists for efficient processing.