Reverse Words in a String II

Updated on 02 July, 2025
Reverse Words in a String II header image

Problem Statement

The problem presents an array of characters, s, and the task is to reverse the sequence of words in-place. Here, a word is defined as a continuous sequence of non-space characters, and these words are distinguished from one another by a single space character within the array. It's crucial to achieve the word reversal without using extra space, meaning the solution must modify the array s directly.

Examples

Example 1

Input:

s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]

Output:

["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2

Input:

s = ["a"]

Output:

["a"]

Constraints

  • 1 <= s.length <= 105
  • s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
  • There is at least one word in s.
  • s does not contain leading or trailing spaces.
  • All the words in s are guaranteed to be separated by a single space.

Approach and Intuition

The core concept for solving this task is to think about the problem in two key steps:

  1. Reverse the entire array: This is the preliminary step where we reverse all characters in the array. This operation positions the words in the approximate desired order but reverses the individual words as well. For instance, reversing ["t","h","e"," ","s","k","y"] entirely would yield ["y","k","s"," ","e","h","t"].

  2. Reverse each word individually: After the entire array has been reversed, each word within will also be reversed. The second step is to correct this by reversing each word in its place. This process restores the correct orientation of characters within each word but retains the overall reversed word order.

Things to consider based on constraints:

  • Since the operation must be performed in-place, techniques like array slicing or using additional arrays for storage are not allowed. Instead, operations will involve swapping elements directly within the input array.
  • Special cases include arrays with only one word and where the first or last characters in the array are space characters. The function should be designed with these in mind, but the constraint assures no leading or trailing spaces, simplifying the operation somewhat.
  • The algorithm needs to handle arrays up to the length of 105, emphasizing the need for an efficient solution, ideally linear in time complexity relative to the number of characters in the array.

This approach ensures that the solution adheres to the in-place requirement effectively by only modifying the array via element swapping and sequential traversals, aiming for a time complexity that is linear, i.e., O(n), where n is the number of characters in the array.

Solutions

  • C++
cpp
class Solution {
public:
    void reverseStringWords(vector<char>& strVec) {
        reverse(strVec.begin(), strVec.end());
    
        int wordStart = 0, wordEnd = 0;
        int length = strVec.size();
    
        while (wordStart < length) {
            while (wordEnd < length && strVec[wordEnd] != ' ') {
                wordEnd++;
            }
    
            reverse(strVec.begin() + wordStart, strVec.begin() + wordEnd);
    
            wordEnd++;
            wordStart = wordEnd;
        }
    }
};

This solution, aimed at the problem of reversing the words in a string using C++, employs an efficient approach to manipulate string data directly in place for enhanced performance and reduced memory usage.

The solution involves the following steps:

  1. Reverse the entire string initially to invert the order of characters.
  2. Iterate over the reversed string to identify individual words separated by spaces.
  3. Reverse each word found to restore its correct order while keeping the overall reversed word order intact.

Key details of the implementation:

  • Utilize the reverse function from the C++ Standard Library for in-place string manipulation.
  • Identify the start and end of each word using a loop, and apply the reverse function to each word independently.

By reversing the entire string first and then each word, the solution achieves the goal of reversing the order of words in the string while maintaining the order of characters within each word. This method avoids the need for additional storage, thus being memory efficient.

  • Java
java
class Solution {
    public void reverseSegment(char[] s, int startIdx, int endIdx) {
        while (startIdx < endIdx) {
            char temporary = s[startIdx];
            s[startIdx++] = s[endIdx];
            s[endIdx--] = temporary;
        }
    }
    
    public void reverseEachWordInArray(char[] s) {
        int length = s.length;
        int startPos = 0, endPos = 0;
    
        while (startPos < length) {
            // find end of the current word
            while (endPos < length && s[endPos] != ' ') ++endPos;
            // reverse current word
            reverseSegment(s, startPos, endPos - 1);
            // adjust to the start of next word
            startPos = endPos + 1;
            ++endPos;
        }
    }
    
    public void reverseWordsInSentence(char[] s) {
        // reverse the entire character array
        reverseSegment(s, 0, s.length - 1);
    
        // then reverse each word in the array
        reverseEachWordInArray(s);
    }
}

This Java solution for reversing the words in a string in-place efficiently manipulates character arrays. Follow these key steps to understand the approach:

  • Define a helper method reverseSegment to reverse a segment within a character array between two indices. This method swaps characters from start to end until the entire segment is reversed.

  • Implement reverseEachWordInArray to handle the reversal of each word individually:

    • Loop through the character array to identify individual words. Words are segments that end with a space character.
    • Apply the reverseSegment method to each word identified.
  • The main method reverseWordsInSentence performs the overall task in two major steps:

    • First, reverse the entire character array to invert the order of all characters, effectively placing all words in their final reversed position in the array.
    • Then, use reverseEachWordInArray to correct the order of characters within each word in the array.

This approach ensures that words are reversed in their position without any additional memory for storage, making the operation space-efficient.

  • Python
python
class Solution:
    def reverse_segment(self, arr: List[str], start: int, end: int) -> None:
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    def reverse_word_by_word(self, arr: List[str]) -> None:
        length = len(arr)
        begin = finish = 0
    
        while begin < length:
            while finish < length and arr[finish] != ' ':
                finish += 1
            self.reverse_segment(arr, begin, finish - 1)
            begin = finish + 1
            finish += 1
                
    def reverseWords(self, s: List[str]) -> None:
        self.reverse_segment(s, 0, len(s) - 1)
        self.reverse_word_by_word(s)

The provided Python solution focuses on reversing the words in a given list of characters, effectively solving the "Reverse Words in a String II" problem without returning any value, as it modifies the list in place. This operation is done by defining and utilizing two main helper functions: reverse_segment and reverse_word_by_word.

Here's how the code achieves its goal:

  • Initial Full Reverse: *Applies the reverse_segment function initially to the entire string. This action reverses the whole array of characters. For example, given "the sky is blue", it transforms the list to "eulb si yks eht".

  • Word-by-Word Reverse:

    • Executes the reverse_word_by_word method, which then processes each word individually. It scans for word boundaries (spaces) and applies reverse_segment to each word segment to restore the original word order while keeping the individual words reversed.

Here's what happens during the execution:

  1. reverse_segment: Takes a segment of the array defined by start and end indices, and reverses the characters within that segment in place using a while loop.
  2. reverse_word_by_word: Iterates through the complete list of characters. For each word detected (delimited by spaces), it applies reverse_segment to reverse back each word in its place.
  3. reverseWords: Combines these functions methodically. It reverses the whole character list first to achieve the reversed word order. Then, it reverses each word to correct the orientation of the characters within words.

This method is both time-efficient and space-efficient as it optimizes in-place operations without utilizing additional memory for another array, fitting well within typical constraints for string manipulation challenges.

Comments

No comments yet.