621. Reversing the Words, Not the Letters
A line of text contains words made of visible characters, separated by one or more spaces. There may also be spaces at the start or the end.
Print the words in reverse order, separated by single spaces, with no space at the start or the end. The letters inside each word are NOT reversed.
the sky is blue -> blue is sky the
hello world -> world hello
a good example -> example good a
## The whole problem is the spaces
Reversing the order of words is easy. Every failing solution fails on the separators:
· a leading space produces an empty first word · a trailing space produces an empty last word · two spaces in a row produce an empty word in the middle · joining with the original spacing reproduces the runs in the wrong places
The output has EXACTLY one space between words and none at the ends, whatever the input looked like.
## Scanning from the right
Walk a pointer backwards. Skip spaces, then find the start of the word that ends there, and take the slice:
j = len-1
while j >= 0:
while j >= 0 and s[j] == ' ': j -= 1 skip the gap
if j < 0: break
i = j
while i >= 0 and s[i] != ' ': i -= 1 find the word start
emit s[i+1 .. j]
j = i
Every character is visited a constant number of times, so this is one linear pass with no splitting and no intermediate list of words.
## The shortcut, and why it is worth knowing both
Most languages will do this in one line: split on whitespace, reverse, join with a single space. A split that discards empty fields handles all four space problems by itself, which is why the one-liner is correct and why the manual version has to be careful.
Write the pointer version anyway. It is the form that survives into languages without a splitting library, and into situations where the text is a stream rather than a string.
## Boundaries
A single word comes back unchanged. A line that is only spaces cannot occur, because the constraints promise at least one word.
## Cost
Time O(n). Space O(n) for the output.
Constraints - `1 ≤ length of the line ≤ 200000` - the line contains at least one non-space character - characters are printable ASCII
Input
One line of text containing at least one word. Words are separated by one or more spaces, and the line may begin or end with spaces.
Output
Print the words in reverse order on one line, separated by single spaces, with no leading or trailing space.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.