Word break with a dictionary and a trie in Python

Why this matters

Many programs must cut text into words. A spell checker splits a line of text into known words. A search box that receives newyorkpizza with no spaces must guess the words to find results. A hashtag reader turns #applepie into two words. Each of these asks the same question: can this string be written as dictionary words placed side by side with nothing left over?

This question is a good first problem for dynamic programming, which means solving small pieces of a problem once, storing each answer in a table, and building bigger answers from the stored ones. You met the idea of storing answers in lessons 1 and 2 of this module. Here the stored answers are simple true or false values, and the table has one slot per prefix of the string.

By the end of this lesson you will be able to decide word break in Python with a table, find one valid split, make the search faster with the longest word length, and use a trie, which is a tree that stores words one letter at a time. You will also see the mistakes that cause errors in this kind of code.

The problem in plain words

Some terms first.

• A string is a piece of text, such as applepen.
• A dictionary here is a list of words that count as valid. The list is given to you. It is not the whole English language.
• A substring is a run of letters taken from inside a string. pen is a substring of applepen, starting at position 5 and ending before position 8. In Python, s[5:8] gives those letters.
• A prefix is a substring that starts at the first letter. apple is a prefix of applepen.
• Positions in Python strings start at 0. The first letter is at position 0, and s[2:5] gives the letters at positions 2, 3 and 4.

The task is to answer one question. Given a string s and a dictionary, can s be split into one or more dictionary words, placed next to each other with no gaps and no letters left over? A word may be used more than once.

Here are two examples.

applepenapple with the dictionary apple and pen can be split as apple + pen + apple. The answer is true.

catsandog with the dictionary cats, dog, sand, and and cat cannot be split. Try cat + sand + og. The last piece og is not a word. Try cats + and + og. Again og is not a word. Every other way ends in a piece that is not in the dictionary. The answer is false.

Start with a question about prefixes

Do not try to find the split all at once. Instead, ask a smaller question for every prefix of the string.

Let ok[k] mean: the first k letters of the string can be split into dictionary words. So ok[0] is about the empty prefix, which has zero letters. An empty prefix can be split into zero words, so ok[0] is true. The final answer is ok[n], where n is the length of the whole string.

The rule that fills the table comes from thinking about the last word. Suppose the first end letters can be split. The last word in that split covers some letters from a position start up to end. The first start letters must then also be splittable, and the piece from start to end must be a dictionary word. So:

ok[end] is true when there is some start below end where ok[start] is true and the piece from start to end is a dictionary word.

Here is the table for applepenapple, which has 13 letters. The prefix column shows the first k letters.

The answer is ok[13], which is true. The table also shows where the split came from. The true entries at 5, 8 and 13 mark the ends of the three words, apple, pen and apple.

Each entry depends only on earlier entries, so one left-to-right pass fills the whole table. Each entry is computed once. This is what makes the method dynamic programming.

Method 1: check every start for every end

The direct version tries every start below each end. It is short and easy to check by hand. The dictionary goes into a set, which can answer "is this string in the set?" in about the same time no matter how many words the set holds. The list ok holds the true and false values.

def can_break_simple(s, words):
    dictionary = set(words)
    ok = [False] * (len(s) + 1)
    ok[0] = True
    for end in range(1, len(s) + 1):
        for start in range(end):
            if ok[start] and s[start:end] in dictionary:
                ok[end] = True
                break
    return ok[len(s)]

Two details matter. First, s[start:end] creates a new string each time it runs, and the cost grows with the length of the piece. Second, break stops the inner loop once ok[end] is set to true. One valid last word is enough for that position.

The method runs two nested loops over the string. For a string of length n, the inner loop runs about n times for each of the n ends, so the work grows with n squared. For a string of 2000 letters, that is about two million checks in the worst case.

Worked example: a split with three words

Here is a second example with a few more steps, the string catsanddog and the dictionary cat, cats, and, sand and dog. The string has 10 letters, at positions 0 to 9:

c a t s a n d d o g

Fill in ok one prefix length at a time.

• ok[0] is true.
• ok[1] (c) and ok[2] (ca) are false. Nothing matches.
• ok[3] (cat) is true, because cat is a word starting at 0.
• ok[4] (cats) is true, because cats is a word starting at 0.
• ok[5] (catsa), ok[6] (catsan) and ok[8] (catsandd) are false. The pieces that end at these positions are not words, and the true positions 3 and 4 do not lead to words here.
• ok[7] (catsand) is true, because sand is a word starting at 3, and ok[3] is true.
• ok[9] (catsanddo) is false.
• ok[10] (catsanddog) is true, because dog is a word starting at 7, and ok[7] is true.

The true prefix lengths are 0, 3, 4, 7 and 10. The method returns true for this input.

The method can also list one valid split. The next section adds that. For this input the split is cat, sand, dog.

Method 2: use the longest word length

The first method checks many starts that cannot possibly work. Suppose the longest word in the dictionary has 4 letters. A piece that ends at end can then start only at end - 1, end - 2, end - 3 or end - 4. Any start further back would make a piece longer than any word. So the inner loop can begin at end - 1 and stop once the start is more than max_len letters back.

def can_break_max_len(s, words):
    dictionary = set(words)
    max_len = max((len(w) for w in words), default=0)
    ok = [False] * (len(s) + 1)
    ok[0] = True
    for end in range(1, len(s) + 1):
        lowest = max(0, end - max_len)
        for start in range(end - 1, lowest - 1, -1):
            if ok[start] and s[start:end] in dictionary:
                ok[end] = True
                break
    return ok[len(s)]

The max(0, end - max_len) line keeps start from going below 0. Without it, range would start below 0, and the slice s[start:end] with a negative start would quietly take letters from the end of the string, which gives a wrong answer with no error. The keyword argument default=0 in max covers an empty dictionary, which has no lengths to compare.

The search now looks backward from the end, so a single-letter word is found on the first try whenever it works. The first method searched forward from position 0, so for a string of many a letters it tried long useless pieces first.

Measuring the work

Work counts are a fair way to compare these methods, because each count is one lookup. They are not seconds. The counts below come from running the functions with a counter added to the inner loop. Every method in this lesson has the same counter, so the numbers are comparable. I did not time the runs, so I make no claim about how long each one takes on a real computer.

The first test uses the dictionary a, aa, aaa, aaaa and b, and the string is 60 letters a followed by one b. The next program prints the counts for the first two methods, and the trie count from the method in the next section. It does not read input.

The output is:

simple: True 1717
maxLen: True 61
trie:   True 295
characters: 61

The simple method made 1717 checks. The length method made 61, one for each position, because the single letter just before each end always matched. The trie method, which comes next, made 295 steps.

A second test used 1000 random words of length 1 to 12 over the ten letters a to j, and a random text of 2000 letters, with a fixed random seed. One run gave about two million checks for the simple method, exactly 2000 for the length method, and 7279 steps for the trie. All three methods returned true. The counts change with the seed and the dictionary. The length method made one check for each position, so its first check matched every time. The trie made more steps than the length method on this input, so fewer steps is not the only thing the trie offers. The next section explains what it does save.

Method 3: a trie walks the dictionary letter by letter

A trie (pronounced "try") is a tree where each step down the tree adds one letter. The words cat, cats and dog are stored like this:

root
 +- c
 |   +- a
 |       +- t   (word: cat)
 |           +- s   (word: cats)
 +- d
     +- o
         +- g   (word: dog)

Each node can have children, one for each letter that continues some word. A node marked as a word means that a dictionary word ends at that node. The path c, a, t spells cat, and the node after t is marked as a word. The path c, a, t, s spells cats, and that node is marked too. Words that share a beginning share the same path, so cat and cats share the first three steps.

In Python, a node can be a small class with two fields: next, a dictionary from a letter to a child node, and is_word, a true or false flag. Here is the code to build the trie and to use it.

class TrieNode:
    def __init__(self):
        self.next = {}
        self.is_word = False
 
 
def build_trie(words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.next:
                node.next[ch] = TrieNode()
            node = node.next[ch]
        node.is_word = True
    return root
 
 
def can_break_trie(s, words):
    root = build_trie(words)
    ok = [False] * (len(s) + 1)
    ok[0] = True
    for start in range(len(s)):
        if not ok[start]:
            continue
        node = root
        for i in range(start, len(s)):
            node = node.next.get(s[i])
            if node is None:
                break
            if node.is_word:
                ok[i + 1] = True
    return ok[len(s)]

The main change from the earlier methods is the direction. Instead of asking "is this piece a word?" for each end, the trie method starts from each start position that is already known to be reachable. It follows the letters of the string one at a time down the trie. Each time it reaches a node marked as a word, it knows that a word ends just after that letter, so it sets ok at that position to true. When there is no child for the next letter, the walk stops. No longer piece from that start can be a word, because no word in the dictionary has those letters as a beginning.

The method get on a dictionary returns None when the key is missing. That is why the walk checks if node is None before it reads node.is_word.

This stopping rule is the reason the trie and the longest word length belong together. A walk can never go deeper than the longest word in the dictionary, because the trie has no path longer than that. So the trie gives the same limit as max_len, without needing the number.

Take the string catsdog with the trie above. Start at position 0. The walk reads c, then a, then t, which is a word. It reads s, which is a word. It then tries to read d from the node for cats. That node has no child for d, so the walk stops after 5 lookups: c, a, t, s, and the failing d.

Finding one valid split

Knowing that a split exists is often not enough. A word break program usually has to return the words too. To do that, store for each position where it was first reached from. Call this list frm. When position end is reached from start, set frm[end] = start. After the table is full, walk backward from the end, reading the words off as you go.

The output is:

['apple', 'pen', 'apple']
['cat', 'sand', 'dog']
['pineapple', 'pen']
[]

The value -1 means "not reached yet". The check frm[i + 1] == -1 makes sure each position records only the first start that reaches it. The list is built with insert(0, ...) so the words come out in the order they appear in the string. The last case gives an empty list, which means no split exists. The function uses an empty list as the answer for "no split", so a caller should check if not parts.

This version stores each trie node as a dictionary with the keys "next" and "is_word", instead of a class. Both forms work. The class version is easier to read, and the dictionary version needs no class.

The third case has two valid splits, pine + apple + pen and pineapple + pen. The method returned the second. Position 9 is first reached from start 0 through the word pineapple, so later paths that reach position 9 are skipped. Another method could return the other split. Both are correct, so a test should check that the returned pieces join back to the input and that each piece is in the dictionary, not that they equal one fixed list.

A check on random cases

A good test program compares the three methods on many random small cases. Each case has a dictionary of one to five words over the letters a and b, and a string of up to 13 letters. For each case it checks that the three methods return the same answer, and that the split from split_one joins back to the string when the answer is true. One seeded run over 3000 cases gave 860 true answers and 2140 false answers, and all three methods agreed on every case.

The cases are random, so the counts change with the seed. This kind of check finds bugs that a handful of hand-written examples miss, because the random inputs hit the edge cases: empty strings, empty dictionaries, words longer than the string, and words that appear more than once.

Common mistakes

Each mistake below is one that a beginner often makes in this problem. The messages are the real ones from running the buggy code with Python 3.14. The paths and line numbers on your machine will differ.

Forgetting ok[0] = True. Every true value in the table comes from an earlier true value. If the first one is false, every value stays false. The method then returns false for every non-empty string, even when the dictionary covers it. There is no error, so this is easy to miss. The fix is one line, and a test with a single word such as apple catches it at once. The next program shows the wrong answer.

The output is False, but apple is a word, so the answer should be True.

Making the list one slot too short. The table needs n + 1 slots, because the prefix of length n has its own answer. A list of length len(s) fails at the last position. For the string abc with the dictionary a, b and c, the buggy version stops with this error:

    ok[end] = True
    ~~^^^^^
IndexError: list assignment index out of range

Index 3 is the position after the last letter, and the list has only indexes 0 to 2.

Not checking for None in the trie. The method get returns None when the key is not present. A walk that does not stop at None then reads a field from nothing. With an empty trie, a buggy version that reads node.is_word straight after get stops with this error. For example, node = root.next.get("a") followed by print(node.is_word) gives:

    print(node.is_word)
          ^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'is_word'

The message says the value was None, which has no attribute named is_word. The fix is to check if node is None before using it, as the walk above does.

Using a list instead of a set for the dictionary. The in test on a list checks each word in turn, so a dictionary of 10,000 words makes every check slow. The answers stay correct, which makes the mistake hard to see. Put the words in a set or in a trie before the loops start.

Assuming the trie is always fewer steps. The measurement above showed the trie made 295 steps where the length method made 61 checks on one input, and more steps than the length method on the random input. The trie is not always less work by count. Its benefit is that each walk stops at the first letter that no word continues, and that the walk never goes deeper than the longest word. Whether that wins in time depends on the dictionary, so measure before you claim a speed-up.

Practice

Each exercise is followed by its answer. Try each one on paper before you read the answer.

Exercise 1. The dictionary is ab, c and abc, and the string is abc. Is the string splittable, and what are the two possible splits?

Show the answer

Yes. The two splits are abc (one word) and ab + c (two words). The method returns true, and split_one returns ['ab', 'c'] or ['abc'], depending on which start reaches the end first. In the code above the walk from position 0 reaches position 3 through abc before ab can reach it through c, so split_one returns ['abc'].

Exercise 2. The dictionary is cat, cats and dog. Walk the trie for the string catsdog from position 0. How many lookups of node.next.get happen before the walk stops?

Show the answer

Five. The lookups are for c, a, t, s and d. The first four succeed. The lookup for d returns None, because no word starts with cats followed by d, so the walk stops there.

Exercise 3. The method can_break_max_len is called with an empty dictionary. What does it return for the empty string, and what does it return for abc?

Show the answer

It returns true for the empty string and false for abc. The empty string is handled by ok[0] = True, and ok[0] is returned when the length is 0. With no words, max_len is 0 because of default=0, so the inner loop never finds a piece for abc, and every position stays false.

Exercise 4. For the string catsanddog and the dictionary cat, cats, and, sand and dog, list every prefix length k from 0 to 10 for which ok[k] is true.

Show the answer

The true lengths are 0, 3, 4, 7 and 10. Length 3 is cat, length 4 is cats, length 7 is catsand, which is cat plus sand, and length 10 is the whole string, which is cat plus sand plus dog. Lengths 1, 2, 5, 6, 8 and 9 are false. The program in the lesson prints the same list.

Exercise 5. Why does split_one set frm[i + 1] only when it is still -1?

Show the answer

Each position should record one start, and the first start that reaches it is kept. Without the check, a later start would overwrite the earlier one. The split would still be valid, because every recorded start really reaches its position. The check keeps the choice fixed and the output predictable.

Summary

• Word break asks whether a string can be cut into dictionary words. The list ok[k] stores the answer for each prefix, and ok[0] is true.
• The rule is: ok[end] is true when some start has ok[start] true and the piece from start to end is a word.
• The longest word length limits how far back each check must look. This cuts the work from all starts to a few starts per position.
• A trie stores words one letter per step. A walk from each reachable start stops at the first missing letter, so it never looks deeper than the longest word.
• To return the words, store the start that first reached each position, then walk backward from the end.