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
- The classic two-step trick: reverse the entire array, then reverse each individual word.
- After reversing the whole array, the word order is correct but every word is spelled backwards.
- Reversing each word restores its spelling without disturbing the order.
- 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 == nsentinel: 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
spliton" "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.