⚡Flashcard Drill➔
NeetCode #28LC-186MediumArrays & HashingNC Algo100
← Back to All Problems

#28 · #186 · Reverse Words in a String II(翻转字符串里的单词 II)

📌 Problem Statement & Constraints

Given a character array s containing a sequence of words separated by single spaces, reverse the order of the words in place. A word is a maximal run of non-space characters, and there are no leading or trailing spaces. Constraints: 1 <= s.length <= 10^5.

💡 Core Algorithmic Approaches

  1. The classic two-step trick: reverse the entire array, then reverse each individual word.
  2. After reversing the whole array, the word order is correct but every word is spelled backwards.
  3. Reversing each word restores its spelling without disturbing the order.
  4. Both steps are O(n) total, and the work is done in place with O(1) auxiliary space -- which is the point of this version versus the string-returning one.

💻 Benchmark Python3 Implementation

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        def rev(i: int, j: int) -> None:
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1

        n = len(s)
        rev(0, n - 1)                      # step 1: reverse the whole array
        start = 0
        for i in range(n + 1):             # n acts as the end sentinel
            if i == n or s[i] == " ":
                rev(start, i - 1)          # step 2: reverse this word back
                start = i + 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): the full reversal is O(n) and the per-word reversals sum to O(n) because the words partition the array.
💾 Space Complexity
O(1) auxiliary: only swap temporaries. A solution that splits into words and rebuilds would use O(n) extra.

⚠️ Interview Pitfalls & Follow-ups

  • Reversing the words first and then the whole array: this gives the same result mathematically, but reversing the whole array first is easier to reason about.
  • Forgetting the i == n sentinel: the final word would never be reversed. Appending a virtual space at the end is the standard fix.
  • Using s.reverse() on the whole array: fine for step 1, but the per-word reversal must be manual since slices of a list cannot be reversed in place with a single call.
  • Returning the array: the signature returns None; the reversal must be in place.
  • Assuming multiple spaces between words: the statement guarantees single spaces, so a simple split on " " is safe -- but the in-place version does not need to care at all.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems