Reverse Words in a String (LeetCode 151)

The problem

You get a string s of words separated by spaces. Return the words in reverse order, separated by exactly one space. The input may have leading spaces, trailing spaces and several spaces between words; the output must have none of those.

Input:  s = "  the sky   is blue "
Output: "blue is sky the"

The four words come out backwards, and all the extra spaces disappear.

How to think about it

Start with the naive attempt. Reverse the whole string character by character: " eulb si yks eht ". The word order is right, but each word is now spelled backwards and the spaces are still messy. Splitting on " " instead of on whitespace gives empty strings between double spaces.

The key insight: work on words, not characters. The problem is really “tokenise, reverse the list of tokens, rejoin”. Python’s str.split() with no argument splits on runs of whitespace and drops leading and trailing spaces, so it returns exactly the words. Reverse that list and join with a single space.

The in-place version, if they ask for O(1) extra space. In a language with mutable strings (or a character array), reverse the whole string, then reverse each word back, then compact the spaces with a read pointer and a write pointer. Two reversals of a word cancel out, leaving only the word order flipped.

Which pattern is this? Plain string manipulation, with a two-pointer in-place variant. The tell is “reverse the order of tokens”: split into tokens first, and the problem becomes reversing a list.

Approach

1. Call s.split() to get the words, with all extra whitespace removed.
2. Reverse the list of words.
3. Join them with " " and return the result.

Solution

def reverse_words(s):
    # split() with no argument drops leading, trailing and repeated spaces
    return " ".join(reversed(s.split()))
# reverse_words("  the sky   is blue ") -> "blue is sky the"

Dry run

On s = " the sky is blue ":

Running the code also gives "example good a" for "a good example", and "" for a string of only spaces.

Complexity

• Time: O(n). Splitting, reversing and joining each touch every character a constant number of times.
• Space: O(n). For the list of words and the output string. The in-place version on a character array uses O(1) extra space.

Edge cases and pitfalls

• Only spaces (" "): split() returns [] and the result is "".
• One word with padding (" hello ") returns "hello".
• split(" ") is a bug. With an explicit separator, Python keeps empty strings for each extra space, so the output has double spaces.
• Reversing characters only gives words spelled backwards. You need the second, per-word reversal.
• Interviewers may ban split. Be ready to scan with two pointers: skip spaces, find the end of each word, and collect words from right to left.

Related problems

• Valid Palindrome (LeetCode 125): two pointers over a string that skip unwanted characters.
• Encode and Decode Strings (LeetCode 271): when splitting on a delimiter is not safe.
• Longest Common Prefix (LeetCode 14): another short string-handling warm-up.