DSA Reversing Words in a Sentence

The problem

A sentence is a sequence of words separated by single spaces. The task is to reverse the order of the words. Each word keeps its own spelling and its own letters in order.

Only the positions of the words change. The first word becomes last, and the last word becomes first. A sentence with one word, and an empty sentence, come back unchanged.

cases = [
    ("the sky is blue", "blue is sky the"),
    ("one two", "two one"),
    ("hello", "hello"),
    ("", ""),
]
for sentence, expected in cases:
    print(repr(sentence), "->", repr(expected))

Read the first row as two separate facts. The word order flips completely. No word is respelled: blue stays blue, and the stays the.

Intuition

The first idea is to reverse the whole sentence. Reversing every character certainly puts the last word first. It also reverses the letters inside every word, which the problem forbids.

sentence = "the sky is blue"
chars = list(sentence)
chars.reverse()
print("all reversed:", "".join(chars))
print("wanted:       blue is sky the")

The reversed text reads eulb si yks eht. The words stand in the right order and every spelling is backwards. That near-miss is useful, though. One more reversal, applied word by word, would restore each spelling while leaving the word order flipped.

Brute force: build the reversed sentence word by word

The straightforward method splits the sentence into a list of words. It then builds the answer by putting each word at the front of a new list, one word at a time. Joining that list with single spaces gives the reversed sentence.

Putting a word at the front of a list is not free. Every word already in the list shifts one place to make room. The counter below counts those shifts.

def reverse_words_brute(sentence):
    words = sentence.split()
    front = []
    shifts = 0
    for word in words:
        shifts += len(front)
        front.insert(0, word)
    return " ".join(front), shifts

result, shifts = reverse_words_brute("the sky is blue")
print("result:", result)
print("shifts:", shifts)

The method is correct and easy to read. Its weakness is the shifting. Each new word at the front pushes every earlier word along, so the shift count grows with the square of the word count.

The optimal solution: reverse twice

Reversing all the characters and then reversing each word back restores every spelling while keeping the flipped word order, and that pair of reversals is the whole solution. It works on a list of characters, in place, with two pointers per reversal.

A helper reverses any range of the character list by swapping its ends and stepping inward. The main function calls it once on the whole list. It then calls it once per word, where a word is the run of characters between two spaces, or between a space and an end of the list.

def reverse_range(chars, lo, hi):
    while lo < hi:
        chars[lo], chars[hi] = chars[hi], chars[lo]
        lo += 1
        hi -= 1

def reverse_words(sentence):
    chars = list(sentence)
    reverse_range(chars, 0, len(chars) - 1)
    start = 0
    for i in range(len(chars) + 1):
        if i == len(chars) or chars[i] == " ":
            reverse_range(chars, start, i - 1)
            start = i + 1
    return "".join(chars)

cases = [
    ("the sky is blue", "blue is sky the"),
    ("one two", "two one"),
    ("hello", "hello"),
    ("", ""),
]
for sentence, expected in cases:
    print(repr(sentence), "->", repr(reverse_words(sentence)), "expected", repr(expected))

All four cases from the start of the article pass. Python strings cannot be changed in place, so the working copy is a list of characters. That list is the only extra structure, and no list of words is built at all.

Walkthrough

Follow the short sentence ab cd ef. It has three two-letter words. The whole-list reversal comes first, then one small reversal per word.

def reverse_range(chars, lo, hi):
    while lo < hi:
        chars[lo], chars[hi] = chars[hi], chars[lo]
        lo += 1
        hi -= 1

chars = list("ab cd ef")
print("start:         ", "".join(chars))
reverse_range(chars, 0, len(chars) - 1)
print("all reversed:  ", "".join(chars))
start = 0
for i in range(len(chars) + 1):
    if i == len(chars) or chars[i] == " ":
        reverse_range(chars, start, i - 1)
        print("word restored: ", "".join(chars))
        start = i + 1
print("final:         ", "".join(chars))

The whole-list reversal gives fe dc ba. The word order is already final at that point: the ef word leads and the ab word trails. Only the spellings are wrong.

Each small reversal fixes one word in place. The spaces never move during the second phase, because each reversal stays inside one word. The final text is ef cd ab.

Complexity

The two-reversal solution takes O(n) time, where n is the number of characters: each character is swapped a constant number of times across the two phases. It takes O(n) space for the character list in Python, because strings are immutable, and O(1) extra space beyond that list.

def brute_shifts(word_count):
    words = ["w" + str(i) for i in range(word_count)]
    front = []
    shifts = 0
    for word in words:
        shifts += len(front)
        front.insert(0, word)
    return shifts

def reversal_swaps(word_count):
    chars = list(" ".join("aa" for _ in range(word_count)))
    swaps = 0
    def rev(lo, hi):
        nonlocal swaps
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            swaps += 1
            lo += 1
            hi -= 1
    rev(0, len(chars) - 1)
    start = 0
    for i in range(len(chars) + 1):
        if i == len(chars) or chars[i] == " ":
            rev(start, i - 1)
            start = i + 1
    return swaps

for w in [4, 8, 16]:
    print("words", w, "brute shifts:", brute_shifts(w), "reversal swaps:", reversal_swaps(w))

The shift counts grow roughly with the square of the word count. The swap counts grow in step with the sentence length. Doubling the words roughly quadruples the shifts and only doubles the swaps.

Edge cases and pitfalls

An empty sentence has no characters to reverse. Both reversal phases run on empty ranges and the answer is empty. A single word is reversed twice, once as a whole and once as the only word, and the two reversals cancel out exactly.

Extra spaces are the pitfall that separates the two routes in this article. The problem as stated uses single spaces, and the in-place route preserves whatever spacing it is given. A split-based route quietly collapses runs of spaces into one. Neither behaviour is wrong in itself, but a solution must know which contract it is serving.

def reverse_range(chars, lo, hi):
    while lo < hi:
        chars[lo], chars[hi] = chars[hi], chars[lo]
        lo += 1
        hi -= 1

def reverse_words(sentence):
    chars = list(sentence)
    reverse_range(chars, 0, len(chars) - 1)
    start = 0
    for i in range(len(chars) + 1):
        if i == len(chars) or chars[i] == " ":
            reverse_range(chars, start, i - 1)
            start = i + 1
    return "".join(chars)

for s in ["", "hello", "one two", "hello, world!"]:
    print(repr(s), "->", repr(reverse_words(s)))
print("double space kept:", repr(reverse_words("the  sky")))
print("split route instead:", repr(" ".join(reversed("the  sky".split()))))

Punctuation travels with its word. The comma stays attached to hello and the exclamation mark stays attached to world, because both are ordinary characters inside their words.