Reverse Words in a String

Problem Statement

You're given a single line of text made up of one or more words. Words are separated by spaces, but the spacing isn't guaranteed to be tidy — there can be more than one space between two words, and the line can start or end with spaces too. Your task is to print those words back out in reverse order (the last word first, the first word last), with exactly one space between each pair of words and nothing extra at the start or end.

Input Format

A single line read from standard input. It may contain leading spaces, trailing spaces, and multiple consecutive spaces between words, but it always contains at least one non-space character.

Output Format

Print one line: the words from the input in reverse order, separated by exactly one space each, with no leading or trailing space.

Example Walkthrough

Take the second sample, This is a test . We scan the line from left to right, skipping over runs of spaces and collecting the characters in between as words. The line starts with two spaces, so we skip them; then we read letters until the next space and get the word This. We skip the next three spaces and read is. We skip one space and read a. We skip three more spaces and read test. Two trailing spaces remain, which we skip, and we've reached the end of the line. That leaves us with the words in their original order: This, is, a, test. To answer the problem we read that list back to front — test, a, is, This — and join the four words with exactly one space between each pair, which gives test a is This, the line we print.

Approach

It's tempting to think about this problem in terms of swapping characters around, the way you might reverse a string in place, but that only reverses the letters, not the order of the words. It also doesn't handle the messy spacing described in the input format. A cleaner way to think about it is to separate the problem into two independent steps: first, figure out what the words actually are, ignoring exactly how much whitespace surrounds them; second, decide how to lay those words back out, which the output format already tells you — exactly one space between each pair, nothing extra at either end.

For the first step, think of scanning the line and looking for maximal runs of non-space characters — each such run is one word. Any run of one or more spaces, wherever it appears (start, middle, or end of the line), is just a separator and gets thrown away rather than preserved. Collecting these runs in the order they appear gives you a list of words with the original spacing already gone. For the second step, walk that list from its last entry back to its first, and place a single space between consecutive words as you output them — never before the first word or after the last one.

Because both steps only ever look at each character of the line a constant number of times (once to find the words, once to write them back out), the whole approach runs in time proportional to the length of the line, and it works the same way no matter how much or how little whitespace the input happens to contain.

Common Mistakes

• Splitting on a single literal space instead of any run of spaces. If you break the line apart wherever you see ' ' without accounting for consecutive spaces, every extra space between two words produces an empty "word" in your list. Reversing and rejoining that list then leaves stray spaces sitting in the middle of your output instead of collapsing them down to one.
• Forgetting about leading and trailing spaces. A line like Hi there has spaces before Hi and after there that aren't part of any word. If your logic doesn't explicitly discard those, the output can end up with an unwanted space at the very start or end, which will not match the expected output even if the words themselves are in the right order.
• Reversing the characters of the whole line instead of reversing the list of words. Doing something like taking the line backwards character by character reverses the letters inside each word as well as their order — This is would become si sihT rather than is This. The order of the words needs to be reversed, but each word's own letters must stay spelled the same way.