Reverse words and trim in Python

Why this matters

A search box cleans up what the user typed before it sends the text to the server. A report generator joins words with exactly one space. A text editor shows the words of a line in reverse when a user chooses to read right to left. Each of these jobs asks the same two questions: which pieces are the words, and how do I put them back together with the spacing I want?

This lesson solves one version of that problem. You are given a sentence, and you must return the same words in the opposite order, with one space between words and no spaces at the start or end. The input " the sky is blue " should become "blue is sky the".

Python has a short answer for this, which is " ".join(reversed(s.split())). This lesson does not stop there. The goal is to see what the library call does for you, so you can write the loop yourself when you need to. You will also use the library answer as a check, because a fast solution that gives the wrong result on an odd input is no use.

The second lesson in this module showed how to build text with a list of pieces. This lesson uses that, and it also uses a list of single characters, which lets you change one character in place. A str cannot be changed, so the in-place method starts by turning the text into a list.

Words, spaces and the two jobs

A word here means a run of characters that are not spaces. A space is a whitespace character, such as the plain space, a tab or a line break. A run is a block of the same kind of character in a row. In "a b" there is one word a, a run of three spaces, and one word b.

The task has two jobs, and they are easier to think about one at a time:

1. Find the words, skipping any run of spaces between them and at the ends.
2. Write the words back in reverse order, with exactly one space between each pair.

Every function in this lesson does these two jobs. They differ in how they hold the text while they work.

Worked example 1: read from the end

The simplest method starts at the last character of the input and walks backwards. It does not need to split the text first.

Take "the sky is blue", which is 15 characters long. The index of the last character is 14, which is the e in blue. The walk does this:

• Skip spaces going left. There are none here, so the index stays at 14.
• Keep going left while the character is not a space. The word runs from index 11 to index 14, which is blue. Copy it into the output.
• Now the index is at 10, the space before blue. The next call to the skip step moves past it to index 9, the s of is.
• Repeat for is, then sky, then the.

Each word is copied once, in the order the walk finds it, which is reverse order. The output starts empty, so the first word needs no space in front of it. Each later word gets one space written before it.

Here is the code:

The output is:

blue is sky the

A few points in this code need explaining.

The variable end remembers where the word finishes. The second inner loop moves i to the left until it finds a space, so after that loop i has passed the start of the word. The word therefore starts at i + 1 and ends at end.

The slice s[i + 1:end + 1] copies the characters from i + 1 up to but not including end + 1. This is the same rule as the slices in the first lesson: the start is included, the end is not. You can read it as "the characters from i + 1 up to end, both included".

The check if pieces: puts a space before every word except the first one written. Without this check the output would start with a space.

Python slices never raise an error for out-of-range ends, and negative indexes count from the end. The loop above is safe because it stops at i >= 0 before every read. A version that forgot the check would not fail with an error. It would read s[-1], which is the last character, and carry on with the wrong text. This is the silent failure from the first lesson, and it is why the check is written before each read.

Worked example 2: remove extra spaces

Before you can reverse anything in place, you need the words sitting next to each other with one space between them. That is a separate job, and it is worth doing on its own first.

The idea is a write pointer and a read pointer. The read pointer r walks forward through the original text. The write pointer w marks where the next kept character goes in the same list. Because w never moves faster than r, the characters you write never overwrite characters you have not read yet.

Take the input "a good example", stored as a list of characters. The steps are:

• Skip spaces with r. Then copy each letter of the word, moving both r and w forward together.
• When the word ends, skip the whole run of spaces with r. Write exactly one space at w before the next word, if there is a word before it.
• Copy the next word and repeat until r reaches the end of the list.

The function below does this, and it returns the length of the cleaned text:

The output is:

w = 14 used = 'a good example'
w = 3 used = 'x y'

The first input has 14 characters in the cleaned text, and the three spaces in the middle have become one. The second input has the leading and trailing spaces removed, so only x y is left, which is 3 characters. The list still has its original length after the function returns, so the code takes only the first w cells with text[:w].

The write pointer never writes over an unread letter. The reason is that w is never ahead of r. Each letter copied moves both pointers by one. Each space written moves w by one while r has already skipped at least one space after the previous word, so r stays ahead.

Worked example 3: reverse the whole list, then each word

Now that the cleaned text is in the list, reversing the word order takes three steps. This is the in-place method, and it uses no extra list of words.

1. Reverse the whole used part of the list. Every character moves to the mirror position, so the words are now in reverse order, but each word is spelled backwards.
2. Walk through the list and reverse each word on its own. A word ends at a space or at the end of the used part.

Take "a good example" (14 characters) as the cleaned input.

Step 1 reverses all 14 characters. a good example becomes elpmaxe doog a. The last word is now first, and the first word is now last, but each word is still backwards.

Step 2 walks the list. It finds the words elpmaxe, doog and a, and reverses each one. The results are example, good and a. Joined with spaces, they give example good a, which is the correct answer.

The helper that reverses a range of the list is short:

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

The line a[lo], a[hi] = a[hi], a[lo] swaps two items. Python evaluates the right side first, so both values are read before either is written, and no temporary variable is needed.

The whole function puts the three steps together:

The output is:

example good a

The loop in step 2 runs up to range(length + 1) on purpose. When i equals length, the loop is one step past the last used cell. That step is what reverses the final word, because the final word has no space after it to trigger the reverse. The check i == length comes first in the condition, so the list is never read at that index.

When length is 0, which happens for an empty string or a string of only spaces, reverse_range(a, 0, -1) does nothing, because lo is not less than hi. The loop runs once with i equal to 0. Since i equals length, it calls reverse_range(a, 0, -1), which again does nothing. The result is the empty string.

The last line, "".join(a[:length]), builds a new string from the first length items. The rest of the list is ignored. This matters because a still has its original length, and its tail still holds the leftover characters from the input.

Checking the answer against a library call

A function like this is easy to get almost right. The best check is a second function that gets the same answer by a different route. Here the second function uses library calls. It uses library calls, so it is short and easy to trust.

def reference(s):
    return " ".join(reversed(s.split()))

The method split() with no argument breaks the text at every run of whitespace, and it drops the empty pieces at the ends. The reversed function gives the words from last to first, and " ".join puts them back together with single spaces. The function returns the empty string when the input has no words, because " ".join([]) is "".

Now the functions can be compared on random input. A program can create thousands of strings made of the letters a to c and spaces, run all three functions on each, and stop at the first difference. The program below does that for 200,000 strings of up to 19 characters. It uses the random module with a fixed seed, so the same strings are made on every run.

The output is:

'the sky is blue' -> 'blue is sky the'
'  hello   world  ' -> 'world hello'
'a good   example' -> 'example good a'
'one' -> 'one'
'' -> ''
'   ' -> ''
random cases checked: 200000 no mismatches

The empty and all-spaces inputs both give '', which is the answer you want. The random test found no difference between the three functions. A random test does not prove that a function is right, but it catches many of the edge cases you would otherwise miss, such as a word at the very start, a word at the very end, and several spaces in a row.

Common mistakes

These mistakes come up often. Each one below shows the symptom you will see, and the fix.

Mistake 1: using split(" ") with one space. This is the most common first attempt. It breaks the text at each single space, so a run of spaces creates empty strings in the result. Splitting "a b" and " x y " on one space prints this output:

The output is:

['a', '', 'b']
['', '', 'x', '', 'y', '']

Each empty string is a piece, and each one becomes an extra join space when you rebuild the text with " ".join. The empty pieces at the ends are kept too, which is different from some other languages. Use split() with no argument, which splits on any run of whitespace and drops the empty pieces, or use a loop like the ones in this lesson.

Mistake 2: forgetting to skip spaces before the first word. A loop that reads the first word without skipping leading spaces writes an empty word at the start. The fix is the skip loop that runs before each word, as the code above does.

Mistake 3: reading below index zero. When the walk from the end goes one step too far, it reads index -1. Python does not raise an error for this, because -1 means "the last character". The walk then keeps going through the text backwards from the end, and it returns text that has no connection to the input. Check i >= 0 before every s[i] read, as the code above does. A read that goes past the start of the text raises an error, which the bad_scan loop below shows. It walks left from index 0 and never finds the stop character:

The output is:

IndexError: string index out of range

The loop first reads s[0] and s[-1], which is the last character, and only fails after the negative index runs past the start of the text.

Mistake 4: writing to the list past the last letter. In step 1, if the write pointer moves ahead of the read pointer, a letter that has not been read yet gets overwritten. The output then has missing or repeated letters. The write pointer must never go past the read pointer. The step-1 code keeps this true because every write happens after a read or at a space that comes before the next word.

Mistake 5: using the whole list instead of length. After step 1, the list still has its original length. If you reverse a from 0 to len(a) - 1, the leftover tail gets reversed into the output. Use length - 1 as the end of the range, and build the result with "".join(a[:length]).

Mistake 6: trying to change a string in place. A str cannot be changed, so this line raises an error:

The output is:

TypeError: 'str' object does not support item assignment

Make a list with list(s) first, change the list, and then build a new string with "".join.

Mistake 7: forgetting that a method returns a new string. s.strip() returns a new string, and the original s does not change. Writing s.strip() on its own line and then printing s shows the spaces still there. Store the result, as in t = s.strip().

Variations and edge cases

Tabs and line breaks. reverse_words_simple treats any whitespace as a separator, because str.isspace() returns True for the plain space, tabs and line breaks. The split() call with no argument does the same. reverse_words_in_place checks only for the plain space, so a tab stays inside a word. For the input one, a tab and two three, the simple function gives three two one, and the in-place function gives three and then one, a tab and two.

Input with one word. The input "solo" has no space at all. The simple function writes solo and stops. The in-place function leaves the word in place, reverses it once in step 1, and then reverses it back in step 2. The output is solo.

Very long input. Both functions make one pass for the cleaning and one or two passes for the reversal, so they take time that grows in a straight line with the length of the input. That is the best you can do, because every character must be looked at at least once. The split version also takes this time, but it creates a new string for each word, so it uses more memory.

Unicode characters. The examples use one character per code point, which covers letters, digits and common symbols. Some characters, such as an emoji with a skin-tone modifier or a letter with a combining accent, are made of more than one code point. Reversing those characters one code point at a time breaks them. The code points and emoji lesson in this module covers that case.

Practice

Try each exercise before you open the answer. Exercises 1 and 2 are short. Exercises 3 to 5 need a little more thought.

1. Predict the output of print(" x y ".split(" ")) before you run it. Then run it and explain each empty string in the result.

Show the answer

The output is ['', '', 'x', '', 'y', '']. The first two empty strings come from the two leading spaces. Each space is a separator, so the text before the first space is empty, and the text between the first and second space is also empty. The x is followed by two spaces, which gives one more empty string before y. The single trailing space at the end gives a final empty string. Python keeps all of these, because split(" ") with a space argument does not drop anything.

2. Write collapse_spaces(s) that removes spaces at the start and end and turns every run of spaces, tabs and line breaks into a single space. Use one list and one loop. Test it on " a b ", which should give "a b", and on "one\ttwo\n\nthree", which should give "one two three".

Show the answer

def collapse_spaces(s):
    pieces = []
    last_was_space = True
    for c in s:
        if c.isspace():
            if not last_was_space:
                pieces.append(" ")
            last_was_space = True
        else:
            pieces.append(c)
            last_was_space = False
    if pieces and pieces[-1] == " ":
        pieces.pop()
    return "".join(pieces)
 
print(repr(collapse_spaces("  a   b  ")))
print(repr(collapse_spaces("one\ttwo\n\nthree")))
print(repr(collapse_spaces("   ")))

The output is 'a b', then 'one two three', then ''. The flag last_was_space starts as true, so leading whitespace is never written. A space is written only when the last thing written was not a space. The final check removes one trailing space if the input ended with whitespace. The library version " ".join(s.split()) gives the same answers.

3. Change reverse_words_simple so that the words are joined with a comma and no space, so "the sky is blue" gives blue,is,sky,the. Explain which line you changed.

Show the answer

The only line that changes is the one that writes the separator. Replace pieces.append(" ") with pieces.append(","). The rest of the function stays the same. The output is blue,is,sky,the, which was checked by running the changed function. The reason one line is enough is that the separator is written in exactly one place, before each word except the first.

4. In the in-place function, explain why the loop in step 2 must run to length inclusive, and not stop one step earlier. Take the input "ab cd" and show what happens with range(length).

Show the answer

The reverse call for a word happens when the loop sees the space after it. The last word has no space after it inside the used part of the list, so only the index length can trigger its reverse. With range(length), the loop stops before that index. Take the input "ab cd". Step 1 reverses the whole list to dc ba. The loop then reverses dc when it reaches the space, and it stops before index 5, so ba stays backwards. The output is cd ba instead of cd ab. Using range(length + 1) lets the loop run once more, at length, and that run reverses the final word.

5. Write last_word(s) that returns only the last word of s, with no spaces. For " one two " it returns two. For "solo" it returns solo. For " " it returns the empty string. Use reverse_words_simple in your answer.

Show the answer

def last_word(s):
    r = reverse_words_simple(s)
    sp = r.find(" ")
    return r if sp < 0 else r[:sp]
 
print(repr(last_word("  one two  ")))
print(repr(last_word("solo")))
print(repr(last_word("   ")))

The output is 'two', then 'solo', then ''. The reversed text starts with the last word of the input, so the first word of the reversed text is the answer. The function finds the first space in the reversed text and returns everything before it. If there is no space, the reversed text is a single word and is returned as it is. For " one two " the reversed text is two one, the first space is at index 3, and the result is two. For " " the reversed text is empty, find returns -1, and the empty string is returned.

Summary

• A word is a run of non-space characters, and the task is to find the words and write them back in reverse order with one space between each pair.
• Reading from the end into a list needs one pass and no copy of the text, and it writes each word once.
• The in-place method first removes extra spaces with a read pointer and a write pointer, then reverses the whole used part, then reverses each word. It uses one list of characters.
• Check any new version against a library call on many random inputs, because the empty input, a single word and runs of spaces are the cases most likely to break.
• Watch for the common errors: split(" ") on a single space keeps empty strings, a negative index in Python reads from the end without an error, and a string cannot be changed in place.