Longest word built one letter at a time

Why this matters

Imagine a word game where you build a word one letter at a time, and every step must give a real word. You can start with a, add p to get ap, add p to get app, and keep going until you reach apple. You cannot start with b if b is not a word, even when banana is in the list. The question is: given a list of words, which is the longest one you can build this way?

This question appears in technical interviews, and it is a good test of whether you can use a trie. The answer needs two things from the trie you already built in lesson 02: the path for each word, and the end-of-word flag that marks where a real word stops. This lesson adds one new rule to the search and uses a depth-first search (a search that goes as deep as it can down one branch, then steps back and tries the next branch) to visit every candidate.

Radix trees and other trie variants are covered in the next lesson, and wildcard search is covered earlier in this module. This lesson uses only the insert and the flag.

Words are paths, and only some stops count

Think of the trie as a map of roads. Each letter is one road segment. Starting at the root and following a, then p, p, l, e, you arrive at the node for apple. Every node is a place on the map, but not every place is a real word. For example, the node for b may exist only because banana was inserted, and b itself may not be a word.

So each node carries one extra answer: does a real word end here? In Python this is a True or False attribute named is_word. It is True at the node for apple if apple was inserted, and False at the node for appl if appl was never inserted.

Here is the rule for this lesson. A word counts only if every shorter prefix of it is also a word. A prefix is the start of a word, so ap is a prefix of apple. For apple to count, the words a, ap, app and appl must all be in the list, and apple must be in the list too.

The trie gives this check almost for free. Walk down from the root, and step into a child only when that child's is_word is True. Every node you reach then has a real word for its path, and every shorter prefix on that path was a word too, because you only stepped through word nodes. You never need to check the prefixes one by one.

Example 1: a small list

Take this list: a, banana, app, appl, ap, apply, apple. Before writing any code, check it by hand.

• a is a word. Its only prefix is itself, so a counts.
• ap is a word, and its prefix a is a word, so ap counts.
• app, appl, apple and apply each have all their prefixes as words, so they count.
• banana does not count, because its first prefix b is not a word.

Two answers have five letters: apple and apply. The rule for ties is that the smaller word in dictionary order wins. The letter e comes before y in the alphabet, so apple is the answer.

The table shows how a depth-first search visits the candidates in this list. It goes down the a branch first.

The last row matters most. The search reaches the child b, sees that is_word is False, and skips the whole banana branch. Nothing below b can count, because b is not a word.

The Python program

The program below holds the trie, inserts a list of words, and returns the answer. It is the complete code for this lesson.

The output is:

apple
world
catsx
z
[]

The first line is example 1. The second line is example 2, and the third is example 3, both below. The fourth line is a one-letter word. The fifth line checks a list where the first letter is not a word, so the answer is the empty string. The brackets show the empty answer clearly.

Each part of the code has one job.

TrieNode holds two things. children is a dictionary that maps a character to the next node. A dictionary finds a value from its key quickly, and here the key is a one-letter string and the value is the child node. is_word is the flag from the previous section.

insert is the insert from lesson 02. It creates a child only when the letter is missing, using if ch not in node.children. After the last letter, the program sets is_word on the final node.

longest_buildable clears the answer and starts the search at the root, with an empty path.

_explore is the depth-first search. For each child of the current node, it does five things:

1. If the child is not a word, skip it. Nothing below a non-word can count.
2. Add the child's letter to path. Now path spells the word at this child.
3. Compare that word with self.best. A longer word wins. If the lengths match, the word that comes first in dictionary order wins. Python compares strings in dictionary order with <.
4. Search below the child, to find longer words that pass through it.
5. Remove the last letter from path, so the next sibling starts from the right place.

Step 5 is called backtracking. The path is a list of single letters. Python strings cannot be changed in place, so the program keeps the letters in a list, and "".join(path) makes a string only when it needs to compare a word. Adding a letter and then removing it costs less than building a new string for every visit, and the code reuses one path for the whole search.

The comparison in step 3 does not depend on the order in which the children are visited. Suppose the search visits apply before apple. When it reaches apple, the lengths match and apple is smaller, so apple replaces apply. If the order were the other way, the result would be the same. The next section shows what happens when the comparison is left out.

The dictionary keeps children in the order they were added, because since Python 3.7 a dictionary remembers insertion order. The tie rule is still needed, because the insertion order is the order of the input list, not the dictionary order of the words.

Example 2: a dead branch that looks like a tie

Take the list w, wo, wor, worl, world, wrong and wr.

The two five-letter words are world and wrong. At first glance they look like a tie, and the smaller one would win. But wrong needs the prefix wro to be a word, and it is not in the list. The trie does have a node for wro, because wrong was inserted through it. That node has is_word set to False, so the search stops there.

The trie looks like this for the part that matters:

root
 └─ w (word)
     ├─ o (word)
     │   └─ r (word)
     │       └─ l (word)
     │           └─ d (word)
     └─ r (word)
         └─ o (not a word)
             └─ n
                 └─ g (word)

Read the picture from the top. The w branch splits into two roads. The o road leads to world, which is buildable. The r road leads to wr, which is a word, and then to wro, which is not. The n and g below wro are never visited. The search reports world, and the output is world.

This example shows that the answer is not simply the longest word in the list. The longest words in this list are world and wrong, and only one of them is buildable.

Example 3: a whole family cut off

Take the list c, ca, cat, cats, catsx, cab, cabin, cabins, cabinet and cabinets.

The longest word in the list is cabinets, with eight letters. It is not buildable, because the prefix cabi is not a word. That cuts off cabin, cabins, cabinet and cabinets together, even though they are all in the trie.

The search goes like this:

• c is a word. Enter it.
• ca is a word. Enter it.
• cab is a word. Enter it. Its child cabi is not a word, so skip it.
• cat is a word. Enter it.
• cats is a word. Enter it.
• catsx is a word. Enter it. It has five letters, which beats cats at four.

The output is catsx. The word catsx is not in any ordinary dictionary, which is fine here: the rule does not ask for real English. It asks only that each prefix is in the list, and the list is the only dictionary.

Running it on a real word list

The EFF large word list is a list of English words, one per line, made for generating random passphrases. On the machine used to test this lesson, a copy was at /usr/share/keepassxc/wordlists/eff_large.wordlist and had 7,772 lines. Any file with one word per line works.

The program above has no file reader, so the simplest way to test it on a real list is to read the file in a second program that calls solve. Put this code in the same file as the program above, after the solve function, and remove the five print lines that test the examples:

import sys
 
path = sys.argv[1]
with open(path, encoding="utf-8") as f:
    words = [line.strip() for line in f if line.strip()]
print("words:", len(words))
print("longest buildable:", solve(words))

Run it with the file path as the argument:

python3 longest_word.py /usr/share/keepassxc/wordlists/eff_large.wordlist

The output is:

words: 7772
longest buildable: 

The answer is the empty string, shown by the blank space after the colon. The reason is simple. Every buildable word needs its first letter to be a word on its own. The shortest word in this list has three letters, so no one-letter word exists, and the search has no starting point. A list like this one is a useful reminder that an empty answer is a real answer, not an error.

Common mistakes

These four mistakes are easy to make when writing this program. Each one was run on a copy of the code, and the output shown is the real output.

Mistake 1: forgetting to check is_word on the child

If the if not child.is_word check is removed, the search walks through non-words. For the example 1 list, the program prints:

banana

The answer banana is wrong, because b is not a word, so banana cannot be built one letter at a time. The fix is to skip any child whose flag is False before doing anything else with it.

Mistake 2: comparing only the length

If the tie rule is removed, and the code only checks len(word) > len(self.best), the answer depends on the order the children are visited. Take the list p, pb, a and ab. The answer should be ab, because ab and pb both have two letters, and ab comes first in dictionary order. The buggy program prints:

pb

The dictionary visits the child p before a, because p was inserted first. So pb is set first. Then ab has the same length, and the length-only rule does not replace it. In a language whose dictionaries did not keep insertion order, the same bug could show up with a different list, or it could hide. Always write the tie rule in the code, and do not rely on the order of the children.

Mistake 3: forgetting to remove the last letter

If the line path.pop() is removed, the letters from one branch stay in path when the search moves on to the next branch. For the example 1 list, the program prints:

applye

The word applye is not in the list. The search went down the y child of appl to apply, and it did not remove the y. The next child, e, was then added after the leftover y, which spells applye. Every time the search steps back up the trie, it must remove the letter it added.

Mistake 4: using get instead of checking for a missing child in the insert

Suppose the insert uses node.children.get(ch). get returns None when the key is missing. The next pass through the loop then tries to read children from None:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
 
 
def insert(root, word):
    node = root
    for ch in word:
        node = node.children.get(ch)
    node.is_word = True
 
 
insert(TrieNode(), "apple")

The output is:

Traceback (most recent call last):
  File "main.py", line 14, in <module>
    insert(TrieNode(), "apple")
    ~~~~~~^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 10, in insert
    node = node.children.get(ch)
           ^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'children'

The first letter a is missing, so get returns None. The second pass then reads children from None. The fix is the if ch not in node.children check from the program above, which creates the missing child before the walk moves on.

Practice

Each exercise has an answer. Try the exercise first, then check your answer.

Exercise 1. Find the answer for the list x, xy, xyz, xyzw and xz.

Show the answer: xyzw. The prefixes x, xy and xyz are all words, so xyzw is buildable and has four letters. The word xz has two letters, so it loses. Nothing is longer than xyzw in this list, so the answer is xyzw.

Exercise 2. Find the answer for the list ten, te, t, tens, tenth and tenths.

Show the answer: tens. The prefixes of tens are t, te, ten, all words. The prefixes of tenth include tent, which is not a word, so tenth and tenths are not buildable. The answer is tens.