186. Reverse Words in a String II

MediumLeetCode

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

How to solve the problem

• In-place Two-Pointer Reverse Approach

Code

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

        n = len(s)
        start = 0
        for i in range(n + 1): # We deliberately let i go up to n without actually accessing s[n]; instead, we use the condition i == n to handle the “last word.”
            if i == n or s[i] == " ":
                l, r = start, i - 1
                while l < r:
                    s[l], s[r] = s[r], s[l]
                    l += 1
                    r -= 1
                start = i + 1

Complexity

• Approach: In-place Two Pointers Approach

• Time complexity: O(n)

  • We reverse the entire array once and then reverse each word, which takes O(n) time

• Space complexity: O(1)

  • We only use a constant amount of extra space for the two pointers