Reverse Words in a String II
Medium · Two Pointers · Explanation and code example
Reverse the Whole String and Then Reverse Each Word
How it works
Reversing the word order might seem complex, but there is a clever trick: reverse the entire string first, then reverse each individual word. When we reverse the whole string, the words end up in the correct order but each word itself is spelled backward. By reversing each word individually, we fix the spelling while preserving the new word order. This two-pass approach elegantly solves the problem in place.
Steps
- Reverse the entire character array using two pointers that swap characters from both ends moving inward.
- Iterate through the array to find each word (delimited by spaces).
- For each word found, reverse just that segment using the same two-pointer swap technique.
- Continue until all words have been reversed.
Complexity
- Time complexity:
O(N), it's two passes along the string. - Space complexity:
O(1)constant space used
where
Nis the length of the inputs
Things to watch for
Reversing in the Wrong Order
The two-step process must be done in the correct order: first reverse the entire string, then reverse each individual word. Doing it in reverse order (reversing each word first, then the whole string) produces the same result, but the logic is less intuitive when thinking about word order reversal.
Incorrect Word Boundary Detection
When finding word boundaries, ensure you correctly handle the transition between words and spaces. Off-by-one errors when determining where a word ends can cause characters to be included in the wrong word or skipped entirely.
Not Handling Edge Cases
Edge cases like a single word with no spaces, or strings that start or end with a space, need careful handling. The algorithm should work correctly regardless of word count or spacing patterns in the input.
Python code example
from typing import List
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)
C++ code example
class Solution {
public:
void reverseWords(vector<char>& s) {
reverse(s.begin(), s.end());
// 'start' points to the beginning of the current word
// 'end' points to the position just after the current word
int start = 0, end = 0;
int n = s.size();
while (start < n) {
// Move 'right' to the position just after the current word
while (end < n && s[end] != ' ')
end++;
// Note: in C++, reverse() operates on [start, end)
// In other words, the leftmost element is included, while the rightmost element is not
reverse(s.begin() + start, s.begin() + end);
// Move 'start' and 'end' to the beginning of the next word
end++;
start = end;
}
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.