186. Reverse Words in a String II - Explanation

Problem Link

Description

Given a character array 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 a single space.

Your code must solve the problem in-place, i.e. without allocating extra space.

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 <= 10^5
• 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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Reverse the Whole String and Then Reverse Each Word

class Solution:
    def reverse(self, l: List[str], left: int, right: int) -> None:
        while left < right:
            l[left], l[right] = l[right], l[left]
            left, right = left + 1, right - 1

    def reverse_each_word(self, l: List[str]) -> None:
        n = len(l)
        start = end = 0

        while start < n:
            # go to the end of the word
            while end < n and l[end] != ' ':
                end += 1
            # reverse the word
            self.reverse(l, start, end - 1)
            # move to the next word
            start = end + 1
            end += 1
            
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # reverse the whole string
        self.reverse(s, 0, len(s) - 1)
        
        # reverse each word
        self.reverse_each_word(s)

Time & Space Complexity

• Time complexity: $O(N)$, it's two passes along the string.
• Space complexity: $O(1)$ constant space used

where $N$ is the length of the input s