We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reverse Words in a String II

Number: 186

Difficulty: Medium

Paid? Yes

Companies: ServiceNow, Microsoft, Apple, Amazon, Uber

Problem Description

Given an array of characters that represents a sentence, reverse the order of the words in-place. A word is defined as a sequence of non-space characters and words are separated by a single space. The transformation must be done without allocating extra space.

Key Insights

  • Reverse the entire array first to obtain the reversed order of characters.
  • Then, reverse each individual word to restore the correct letter order.
  • Doing so leverages the two-pointer technique for in-place reversals.
  • This method accomplishes the goal in O(n) time while using O(1) extra space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution employs a two-step reversal process using the two-pointer technique. First, reverse the entire character array to reverse the overall order of characters. Although this reverses both the words and the letters in each word, it sets up the scenario where each word's letters are in reverse order. The next step is to iterate through the array and locate each word (using the space character as a delimiter) and then reverse each word individually to correct its letter order. This process is done in-place without any additional data structures, conserving space.

Code Solutions

def reverse_range(s, left, right):
    # Reverse the elements in s from index left to right.
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

def reverseWords(s):
    # Step 1: Reverse the entire array.
    reverse_range(s, 0, len(s) - 1)
    
    n = len(s)
    start = 0
    # Step 2: Reverse each word to correct their order.
    for i in range(n + 1):
        if i == n or s[i] == ' ':
            reverse_range(s, start, i - 1)
            start = i + 1
← Back to All Questions