186. Reverse Words in a String II

MediumTwo PointersString
Leetcode Link

Problem Description

The problem provided is one of reversing the order of words within a character array s. Each word within the array is defined as a contiguous sequence of characters without spaces, and each word is separated by a single space. The key constraint is that the reversal of the word order must be done in-place, which means the solution cannot use additional memory to store a new array or other data structure.

Intuition

To solve this problem, the intuition is to think about the desired end state: we want the words in reverse order, but each word itself should remain in its original order. An efficient way to achieve this is by applying a two-step process:

  1. Reverse each individual word.
  2. Reverse the entire character array.

Step 1 ensures that when we perform Step 2, each word will appear in the correct order since they were individually reversed in the first step.

Implementing Step 1 involves iterating over the character array and reversing characters within each word boundary, defined by spaces. When a space is encountered, it signals the end of the current word, prompting a reversal of all characters from the start of that word to the character immediately before the space.

For the last word, since there’s no trailing space, a check is needed to trigger the reversal when reaching the end of the array.

After all words are individually reversed, Step 2 simply reverses the entire array from start to end. As each word is already correctly ordered internally, this step places the words in the reverse order.

The solution employs helper method reverse that takes a subsection of the array s between indices i and j, swapping the elements at i and j, then moving i forward and j backward, repeating this process until the subsection is completely reversed.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

Solution Approach

The solution approach follows a systematic process:

  1. Initialize Pointers: We start by initializing two pointers, i and j, along with n that holds the length of the character array s. Here, i will serve as the start index of a word, and j will iterate through the array to find the end of a word.

  2. Iterate Through s: We begin iterating over the array with j. The loop continues until j has reached the end of the array.

  3. Reverse Individual Words: As j encounters a space, we realize that it marks the end of a word. At this point, we call the reverse helper function with the current start index i and the end index j - 1. After the reversal of the current word, we move i past the space to the beginning of the next word (i = j + 1).

    • The reverse helper function takes two indices and reverses the subsection of s between these indices. It does this by swapping the elements at i and j, then moves i forward and j backward, repeating the process until i meets or passes j.

  4. Edge Case for Last Word: Since there’s no trailing space after the last word, the condition j == n - 1 checks if j has reached the end of the array, signaling the end of the last word, and a reversal is performed for this last word segment.

  5. Reverse Entire Array: Once all words are reversed, the final step is to reverse the entire character array. This is again done by calling the reverse function with the indices 0 and n - 1.

This algorithm does not use any extra space and operates entirely in-place, modifying the original array to achieve the desired result. The data structure used is simply the input array, and the algorithm leverages the two-pointer technique to identify and reverse each word, followed by the reversal of the entire array. The reversing of elements within the array is based on the classic pattern of using a temporary variable to swap two elements, a fundamental operation in many sorting and reversing algorithms.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's use a simple example to illustrate the solution approach. Suppose we have an array s representing the sentence: "the sky is blue"

The initial state of the array s:

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

Now, let's walk through the process:

  1. Initialize Pointers:

    • We initialize a pointer i at 0 and n as the length of the array s, which is 15.

  2. Iterate Through s:

    • We start iterating forward through the array with a pointer j. Initially, j is also at 0.

  3. Reverse Individual Words:

    • As j moves forward, it encounters the first space at j = 3. This means the first word "the" (from i = 0 to j - 1 = 2) needs to be reversed. Using the reverse helper function, the array now looks like this: 
      1['e', 'h', 't', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e']
    • i is then updated to j + 1, which is 4, the start of the next word "sky".

  4. Continue Iterating and Reversing Words:

    • This process is repeated for the remaining words. After reversing "sky" and "is", the array looks like: 
      1['e', 'h', 't', ' ', 'y', 'k', 's', ' ', 's', 'i', ' ', 'b', 'l', 'u', 'e']
    • When j reaches the end of the array after "blue", j = n - 1, it triggers the last reversal from i = 11 to j = 14, resulting in: 
      1['e', 'h', 't', ' ', 'y', 'k', 's', ' ', 's', 'i', ' ', 'e', 'u', 'l', 'b']

  5. Reverse Entire Array:

    • Finally, we reverse the entire array from 0 to n - 1. After this, the array s looks like: 
      1['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']

Now, the character array s correctly represents the sentence "blue is sky the", with the words in reverse order, and each word internally in the correct order. All this has been achieved in-place, without using any additional memory for a new array or data structure.

Solution Implementation

1class Solution:
2    def reverseWords(self, s: List[str]) -> None:
3        """
4        This method reverses the words in the input list in-place.
5      
6        Parameters:
7        s (List[str]): A list of characters representing a string with words
8                        separated by single spaces.
9        """
10
11        def reverse_partial(section: List[str], start: int, end: int) -> None:
12            """
13            Helper function that reverses a substring of the list in-place.
14
15            Parameters:
16            section (List[str]): The list of characters which substring to be reversed
17            start (int): The starting index of the substring
18            end (int): The ending index of the substring
19            """
20            while start < end:
21                section[start], section[end] = section[end], section[start]
22                start += 1
23                end -= 1
24
25        length = len(s)
26        # Initialize the starting index of the current word
27        word_start = 0
28        # Traverse the list of characters
29        for idx in range(length):
30            # If a space is found, reverse the word before the space
31            if s[idx] == ' ':
32                reverse_partial(s, word_start, idx - 1)
33                # Update the starting index for the next word
34                word_start = idx + 1
35            # If end of the list is reached, reverse the last word
36            elif idx == length - 1:
37                reverse_partial(s, word_start, idx)
38      
39        # Reverse the whole modified list to get words in correct order
40        reverse_partial(s, 0, length - 1)
41
1class Solution {
2  
3    // Function to reverse words in place within a character array
4    public void reverseWords(char[] str) {
5        int n = str.length;
6
7        // First, reverse each word in the array
8        for (int start = 0, end = 0; end < n; ++end) {
9            if (str[end] == ' ') {
10                // When we find a space, reverse the previous word
11                reverse(str, start, end - 1);
12                // Move to the start of the next word
13                start = end + 1;
14            } else if (end == n - 1) {
15                // If this is the end of the last word, reverse it
16                reverse(str, start, end);
17            }
18        }
19
20        // After all words are reversed, reverse the entire array to put words into the correct order
21        reverse(str, 0, n - 1);
22    }
23
24    // Helper function to reverse a section of the character array from index i to j
25    private void reverse(char[] str, int i, int j) {
26        // Swap characters from the starting and ending indices until they meet in the middle
27        while (i < j) {
28            char temp = str[i];
29            str[i] = str[j];
30            str[j] = temp;
31            i++;
32            j--;
33        }
34    }
35}
36
1#include <vector>
2#include <algorithm>  // for std::swap
3
4class Solution {
5public:
6    // Function to reverse words in a given character array.
7    void reverseWords(std::vector<char>& s) {
8        int n = s.size(); // Get the size of the character array
9        // Iterate through the array to find words and reverse them
10        for (int start = 0, end = 0; end < n; ++end) {
11            if (s[end] == ' ') {
12                // A word is found, reverse it
13                reverse(s, start, end - 1);
14                // Update 'start' to the next word's starting index
15                start = end + 1;
16            } else if (end == n - 1) {
17                // Last word is found, reverse it
18                reverse(s, start, end);
19            }
20        }
21        // After reversing all the words individually, reverse the entire array to get the final result
22        reverse(s, 0, n - 1);
23    }
24
25    // Helper function to reverse characters in the array between indices i and j.
26    void reverse(std::vector<char>& s, int i, int j) {
27        // Swap characters from both ends moving towards the center
28        while (i < j) {
29            std::swap(s[i], s[j]);
30            ++i;
31            --j;
32        }
33    }
34};
35
1// Function to reverse a portion of the array between indices start and end.
2function reverse(arr: string[], start: number, end: number): void {
3    while (start < end) {
4        // Swap elements at indices start and end.
5        let temp = arr[start];
6        arr[start] = arr[end];
7        arr[end] = temp;
8        start++;
9        end--;
10    }
11}
12
13// Function to reverse the words in a given character array.
14function reverseWords(s: string[]): void {
15    const n: number = s.length; // Get the size of the character array
16
17    // Iterate through the array to find words and reverse them.
18    let start: number = 0;
19    for (let end = 0; end < n; end++) {
20        // Check if the current character is a space or if we're at the end of the array.
21        if (s[end] === ' ' || end === n - 1) {
22            // Calculate the position to end the reversal (consider the last word case).
23            let reverseEnd = (s[end] === ' ') ? end - 1 : end;
24            // Reverse the current word.
25            reverse(s, start, reverseEnd);
26            // Update 'start' to the next word's starting index.
27            start = end + 1;
28        }
29    }
30
31    // After reversing all the words individually, reverse the entire array to get the final result.
32    reverse(s, 0, n - 1);
33}
34
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The given Python code is designed to reverse the words in a string in-place. Here's the analysis of its complexity:

Time Complexity:

To analyze the time complexity, we observe each part of the code:

  • The reverse function is a part of the total operation, which is called for each word and once for the entire string. It takes O(k) time for each word, where k is the length of that word, and O(n) for the entire string, where n is the total length of the input string.

  • The while loop runs through each character in the string, which takes O(n) time.

Combining these, each character is involved in two operations: once in the main loop, and once when its word is reversed. Including the final reversal of the entire string, we have:

  • For each word of length k: O(k)
  • For the entire string: O(n)

Since the sum of the lengths k of all words is n, we can order these operations as O(n) + O(n) = O(2n). However, in Big O notation, we would drop the constant to simplify the expression to O(n).

Space Complexity:

  • No additional space is needed except for a few variables (i, j, n), since the reversal is done in place.

  • The reverse function does not use any additional space and is performed in place.

Hence, the space complexity is O(1), which indicates constant space usage.

In conclusion, the code has a time complexity of O(n) and a space complexity of O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫