{x}
blog image

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.

 

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution Explanation for Reverse Words in a String

This problem involves reversing the order of words in a given string. The key challenges are handling leading/trailing spaces and multiple spaces between words. The optimal solution should achieve this with linear time complexity O(n) and ideally, constant extra space O(1) if the language allows in-place modification. However, most solutions below achieve O(n) time and O(n) space.

Approach 1: Two Pointers (Detailed)

This approach iterates through the string using two pointers:

  1. Outer Loop (Pointer i): Skips leading spaces and finds the start of a word.
  2. Inner Loop (Pointer j): Finds the end of the current word by iterating until a space is encountered.
  3. Word Extraction: The substring between i and j represents a word, which is added to a list (words).
  4. Reverse and Join: After processing all words, the words list is reversed, and its elements are joined with single spaces to form the final reversed string.

Time Complexity: O(n) - The string is traversed once in the outer loop, and the reverse operation takes O(m) where m is the number of words (m <= n). Therefore, the overall complexity remains linear.

Space Complexity: O(n) - In the worst case, the words list could store all characters of the input string (if each character is a separate word).

Approach 2: Using String Split (Simpler, but potentially less efficient)

This approach leverages built-in string functions:

  1. Split: The input string is split into a list of words using s.split() (or equivalent). The trim() method is used to handle leading and trailing spaces, and a regular expression (\s+) ensures that multiple spaces are treated as single delimiters.
  2. Reverse: The resulting list of words is reversed using reversed() (or equivalent).
  3. Join: The reversed list of words is joined back into a string with spaces.

Time Complexity: O(n) - Splitting, reversing, and joining operations typically have linear time complexity. The efficiency depends on the underlying implementation of the string manipulation functions used.

Space Complexity: O(n) - Similar to Approach 1, the intermediate list of words could occupy linear space.

Code Examples (Multiple Languages)

The previous response provided code examples in several languages implementing both approaches. The comments within those code snippets further explain the logic. Here's a summary of languages covered:

  • Python3
  • Java
  • C++
  • Go
  • TypeScript
  • Rust
  • C#

These examples demonstrate how both approaches can be implemented in various programming languages. The choice between the two approaches may depend on factors such as language features, readability preferences, and potential performance variations for very large inputs (though in most cases, the difference would be negligible). Approach 2 (string splitting) is often considered more concise and easier to read.