Reverse Words In String

Tags

Reverse Words In String

Category

Strings

Difficulty

Medium

Problem Statement

Given a string of words separated by spaces, reverse the order of the words. The function should handle multiple spaces between words and leading/trailing spaces, preserving the exact whitespace structure but in reversed order.

Intuition

Rather than splitting on spaces (which loses information about multiple consecutive spaces), we can treat the string as a sequence of "tokens" where each token is either a word (consecutive non-space characters) or a whitespace segment (consecutive space characters). By collecting these tokens and reversing the entire list, we preserve the original spacing structure while reversing the word order.

Approach

  1. Traverse the string and identify alternating segments of words and spaces.
  2. Store each segment (whether word or spaces) in a list.
  3. Reverse the list of segments.
  4. Join all segments together to form the result string.

Alternatively:

  1. Reverse the entire string character by character.
  2. Then reverse each individual word in place.
  3. This approach works well for in-place reversal in mutable character arrays.

Pseudocode

function reverseWordsInString(string):
    tokens = []
    i = 0
    while i < len(string):
        if string[i] == ' ':
            j = i
            while j < len(string) and string[j] == ' ':
                j += 1
            tokens.append(string[i:j])
            i = j
        else:
            j = i
            while j < len(string) and string[j] != ' ':
                j += 1
            tokens.append(string[i:j])
            i = j
    reverse(tokens)
    return join tokens with ""

Time & Space Complexity

  • Time: O(n) where n is the length of the string. We traverse the string once to tokenize and then reverse the token list.
  • Space: O(n) to store the tokens and build the result string.

Key Insights

  • Treating spaces as their own tokens preserves the exact whitespace structure when reversing.
  • A simple split-by-space approach would lose information about consecutive spaces.
  • The in-place approach (reverse all, then reverse each word) achieves O(1) extra space in languages with mutable strings.

Edge Cases

  • Empty string: return an empty string.
  • String with only spaces: return the same string of spaces.
  • Single word with no spaces: return the word unchanged.
  • Leading and trailing spaces: they become trailing and leading spaces respectively after reversal.
  • Multiple consecutive spaces between words: the space segments are preserved in their reversed positions.

Linked mentions