Reverse Words in a String
WHAT IT SAYS
Reverse the order of the words in a string, collapsing any extra whitespace so the result has single spaces and no padding.
WHAT IT'S REALLY ASKING
"Reverse the whole string and look at what you get: the words are suddenly in exactly the right order, but each one is spelled backwards. That is a strange kind of half-solved — so what is the other half, and why is it the same operation, applied smaller?"
Split, reverse the list, join
O(n) time, O(n) spaceSplit on whitespace, discard the empty tokens that extra spaces produce, reverse the list of words, and join them with single spaces.
WHERE THE WORK IS WASTED — The token list is a second full copy of the input, and it exists only so that you can say 'reverse this list' — an operation the string was perfectly capable of performing on itself. Every character gets copied out into a token, then copied again into the result buffer: 2n characters of copying to perform a rearrangement whose every destination was computable in place. In a language with immutable strings this is unavoidable; in one with a mutable buffer it is a rented crutch.
Reversing flips block order and block contents — so reverse twice.
The identity to hold on to is this: reversing a concatenation reverses the ORDER of the pieces and also reverses each piece. reverse(A . B) = reverse(B) . reverse(A) Apply it to the whole sentence W1 W2 ... Wk. Reversing every character gives you reverse(Wk) ... reverse(W2) reverse(W1). Read that carefully: the words are now in precisely the order you wanted — the last word first — because reversal flipped the blocks. But each block is internally backwards, because reversal does not respect word boundaries; it does not know they exist. So one reversal did exactly half the job, and it did the half that is hard to do in place (moving whole words around). The half that remains — un-scrambling each word — is the SAME operation, applied at a smaller scale: reverse each block, and since reversing twice is the identity, each word snaps back to itself while staying where the big reversal put it. And the reason this costs no memory is the same reason it does for rotating a matrix: a reversal is nothing but a set of independent swaps, pairing each element with its mirror. Swaps need no scratch space. You have factored a complicated permutation — 'reorder the blocks, preserve their contents' — into two applications of the simplest one there is.
Reverse everything, then reverse each word
O(n) time, O(1) extra space, given a mutable character bufferReverse the entire character buffer. Then sweep it with a write pointer, copying each maximal run of non-space characters into place with exactly one separating space — which trims and collapses all the whitespace for free — and reversing each run as you finish writing it. Truncate the buffer at the write pointer.
Factor the Permutation
YOU'LL SEE IT AGAIN WHEN
- The transformation reorders blocks while preserving what is inside them — a rotation, a word-order flip, a cyclic shift.
- It must happen in place, and the obvious answer is 'copy the pieces out and reassemble them'.
- A cheap involution is available (a reversal, a transpose, a swap), and applying it at two different scales might compose into exactly the thing you want.