151. Reverse Words in a String - Detailed Explanation

Problem Statement

Description:
Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The input string may contain leading or trailing spaces, and multiple spaces between words. The returned string should have the words in reverse order and be trimmed so that there is only a single space between words.

Examples:

• Example 1:

  • Input: "the sky is blue"
  • Output: "blue is sky the"
  • Explanation: The words are reversed.

• Example 2:

  • Input: " hello world "
  • Output: "world hello"
  • Explanation: The leading and trailing spaces are removed, and only a single space separates the words in the reversed string.

• Example 3:

  • Input: "a good example"
  • Output: "example good a"
  • Explanation: Multiple spaces between words are reduced to a single space in the final output.

Constraints:

• The input string may contain extra spaces.
• Words are separated by one or more spaces.
• The output should have no leading or trailing spaces, and words must be separated by a single space.

Hints Before You Begin

• Hint 1:
  Think about how you can separate the string into words. Consider using a built-in split operation that automatically handles multiple spaces and trims leading/trailing spaces.

• Hint 2:
  After splitting the string into words, determine how to reverse the order of the list of words efficiently.

• Hint 3:
  Finally, join the reversed list of words back into a single string using a single space as the delimiter.

Approaches to Solve the Problem

1. Brute Force Approach Using Split and Reverse

Idea:

• Step 1: Split the input string into words. Most languages offer built-in functions that split a string on whitespace, automatically handling multiple spaces.
• Step 2: Reverse the list of words.
• Step 3: Join the reversed list using a single space.

Benefits:

• This approach is straightforward and leverages built-in functions.
• It naturally handles trimming and multiple spaces.

Drawbacks:

• This solution uses extra space for storing the list of words.

2. In-Place Reversal (Advanced Approach)

Idea:

• Step 1: Remove extra spaces by trimming and compressing multiple spaces into one.
• Step 2: Reverse the entire string.
• Step 3: Reverse each word in the reversed string to restore the correct word order.

Benefits:

• This approach can be done in-place (if the language permits mutable strings or by using a character array) and may use less extra space.

Drawbacks:

• The in-place approach is more complex to implement and prone to errors with boundary conditions.

For most interview settings, the split-reverse-join method is acceptable and easier to understand.

Code Implementations

Python Code Implementation