Word break with a dictionary and a trie

Why this matters

Some questions ask you to cut a long piece of text into smaller pieces that each belong to a known list. A search engine that reads #catsanddog as three words does this. So does a phone keyboard that guesses a word split in a language with no spaces, and a program that checks whether a web address is made of known words. The question in these cases is simple: can the whole text be cut into known pieces, yes or no?

This lesson solves that yes or no question with dynamic programming, which means you solve small pieces first and store each answer so you never solve the same piece twice. The table idea from the memoization lesson in this module is the starting point. You also need C++ strings, std::vector and std::unordered_set, which you met in the strings and STL lessons. The trie part uses the idea from the tries module, but you do not need that module to follow the steps, because the trie is built and explained here.

The question in plain words

You are given a string s and a list of words called the dictionary. You must answer one question: can s be written as one or more dictionary words placed next to each other with nothing between them?

Take this example. The dictionary holds five words: cat, cats, and, sand, dog. The string is catsanddog. The answer is yes, because the string can be cut as cat then sand then dog. It can also be cut as cats then and then dog. You only need one cut that works. The answer is no for catsandcow, because nothing in the dictionary covers the last three letters cow.

Each cut is a split. A split is valid when every piece is in the dictionary. We will count from zero and number the positions of the string. The first character is at position 0, and the last one in catsanddog is at position 9. The string has n characters, and n is 10 here. A prefix is the start of the string up to some point. The first i characters form the prefix of length i. In C++ you write that as s.substr(0, i).

Pieces are contiguous. You cannot skip a letter, and you cannot reorder letters. The dictionary words are also used exactly as written, so Cat is not cat. In the examples in this lesson, all letters are lowercase.

Trying every cut first

Before any table, think about the direct way. Start at the first character. Try every dictionary word that matches at that spot. For each match, move past it and repeat from the new spot. If you reach the end of the string, the answer is yes. If a spot has no match that leads to the end, back up and try another word.

This is the recursive search idea. It works, but it is slow. The reason is that many routes meet at the same spot. In catsanddog, the route cat then sand and the route cats then and both reach a point where the rest of the string is dog. The search checks dog twice. On a string made of one letter repeated many times, with a dictionary of short words, the number of routes grows very fast, and the same spots are checked again and again.

Dynamic programming fixes this by solving each spot once and writing the answer down. The table that stores those answers is the next step.

Step 1: a table of prefixes

Define a table ok with n + 1 entries. The entry ok[i] is true when the first i characters of s can be split into dictionary words. Read that sentence twice, because the whole method depends on it. ok[i] says nothing about the rest of the string. It only says whether the prefix of length i works.

Two facts start the table:

• ok[0] is true. The empty prefix has zero pieces, and zero pieces is a valid split. This is the base case, the answer you know without any work.
• The answer you want is ok[n], the whole string.

The rule that fills the other entries is this. The prefix of length i works when there is some earlier point j, with j less than i, such that:

• the prefix of length j works, so ok[j] is true, and
• the piece from j up to i is a dictionary word, so s.substr(j, i - j) is in the dictionary.

The last piece is the one that ends at i. The rule says that the earlier part must already be splittable and the last piece must be a word. Every split of the prefix ends with some last piece, so this covers every case.

A worked example by hand

Use catsanddog with the five words above. The string has these characters at these positions.

Start with ok[0] true. Now fill the entries from left to right.

• ok[1] is the prefix c. Starting at j = 0, the piece c is not a word. There is no other j to try, so ok[1] is false.
• ok[2] is the prefix ca. The piece from j = 0 is ca, not a word. From j = 1, ok[1] is false. So ok[2] is false.
• ok[3] is the prefix cat. From j = 0 the piece is cat, which is a word, and ok[0] is true. So ok[3] is true.
• ok[4] is the prefix cats. From j = 0 the piece cats is a word. So ok[4] is true.
• ok[5] is the prefix catsa. Check each j. At j = 0, the piece is catsa, not a word. At j = 3, ok[3] is true, but the piece sa is not a word. At j = 4, ok[4] is true, but the piece a is not a word. So ok[5] is false.
• ok[6] is the prefix catsan. The usable earlier points are j = 3 and j = 4. The pieces san and an are not words. So ok[6] is false.
• ok[7] is the prefix catsand. At j = 3, ok[3] is true and the piece sand is a word. So ok[7] is true.
• ok[8] is the prefix catsando. The usable earlier points are j = 3, j = 4 and j = 7. The pieces are sando, ando and o. None is a word. So ok[8] is false.
• ok[9] is the prefix catsandog. The usable points are j = 3, j = 4 and j = 7. The pieces are sandog, andog and og. None is a word. So ok[9] is false.
• ok[10] is the whole string. At j = 7, ok[7] is true and the piece dog is a word. So ok[10] is true.

The final table is T F F T T F F T F F T. The answer is ok[10], which is true. The split that the table found is cat, sand, dog, because ok[3] leads to ok[7] through sand, and ok[7] leads to ok[10] through dog.

The code for the table

Here is the first version in C++. It tries every point j for every prefix length i. It uses an unordered_set, which is a hash set. A hash set can answer "is this string in the set?" in about one step on average, no matter how many words it holds.

#include <cstddef>
#include <iostream>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
 
// Returns whether s can be split, and how many dictionary lookups were made.
std::pair<bool, std::size_t> wordBreakAllSplits(const std::string& s,
                                                const std::vector<std::string>& words) {
    std::unordered_set<std::string> dict(words.begin(), words.end());
    const std::size_t n = s.size();
    std::vector<bool> ok(n + 1, false);
    ok[0] = true;
    std::size_t lookups = 0;
    for (std::size_t i = 1; i <= n; ++i) {
        for (std::size_t j = 0; j < i; ++j) {
            if (!ok[j]) continue;
            ++lookups;
            if (dict.contains(s.substr(j, i - j))) {
                ok[i] = true;
                break;
            }
        }
    }
    return {ok[n], lookups};
}
 
int main() {
    const std::vector<std::string> dict = {"cat", "cats", "and", "sand", "dog"};
    for (const std::string s : {"catsanddog", "catsandcat", "pineapple"}) {
        auto [answer, lookups] = wordBreakAllSplits(s, dict);
        std::cout << s << ": " << std::boolalpha << answer
                  << " (lookups: " << lookups << ")\n";
    }
}

dict.contains is a C++20 member function. Older code uses dict.count(word) > 0, which means the same thing. The break stops the inner loop as soon as one split works, because one valid split is enough. The continue skips any j whose prefix is not splittable, since those cannot start a valid split.

Compile it with g++ -std=c++20 -Wall -o wordbreak wordbreak.cpp and run it. The output is:

catsanddog: true (lookups: 24)
catsandcat: true (lookups: 24)
pineapple: false (lookups: 9)

The lookups number counts how many times the program made a substring and checked it against the set. It is a measure of work. It is not a timing, so use it to compare methods on the same input.

The cost of this version is high. There are about n * n / 2 pairs (j, i). For each pair, s.substr copies up to n characters and the hash set hashes them. In the worst case the total work is about n cubed. For a 3,000 character string that is far too much. The next steps reduce this.

Step 2: stop at the longest word

Look at the dictionary again. The longest word is cats or sand, with 4 letters. Any piece that ends at i and is a word must be at most 4 letters long. So the start point j can never be more than 4 positions before i. The check j = i - 4 is the earliest one that could help, and every j before it makes a piece longer than any word.

Let maxLen be the length of the longest word. For each i, only check j from i - maxLen up to i - 1. If i - maxLen is less than zero, start at zero. The earlier points can never produce a word, so skipping them does not change the answer.

Here is the function with the change. The only change in the loop is where the inner loop starts.

// Returns whether s can be split, and how many dictionary lookups were made.
std::pair<bool, std::size_t> wordBreakMaxLen(const std::string& s,
                                             const std::vector<std::string>& words) {
    std::unordered_set<std::string> dict(words.begin(), words.end());
    std::size_t maxLen = 0;
    for (const auto& w : words) maxLen = std::max(maxLen, w.size());
 
    const std::size_t n = s.size();
    std::vector<bool> ok(n + 1, false);
    ok[0] = true;
    std::size_t lookups = 0;
    for (std::size_t i = 1; i <= n; ++i) {
        const std::size_t lowest = i > maxLen ? i - maxLen : 0;
        for (std::size_t j = lowest; j < i; ++j) {
            if (!ok[j]) continue;
            ++lookups;
            if (dict.contains(s.substr(j, i - j))) {
                ok[i] = true;
                break;
            }
        }
    }
    return {ok[n], lookups};
}

The line const std::size_t lowest = i > maxLen ? i - maxLen : 0; is the important one. It guards against a subtraction that would go below zero. The reason for the guard is explained in the mistakes section, because it is the most common bug in this kind of code.

Running this version on the same three strings gives the same answers and fewer lookups:

catsanddog: true (lookups: 13)
catsandcat: true (lookups: 13)
pineapple: false (lookups: 4)

For catsanddog the count drops from 24 to 13. The gap grows as the string gets longer, because the first version checks every earlier point and this one checks at most maxLen of them.

The cost is now about n * maxLen pairs, and each substring has at most maxLen characters. So the total work is about n * maxLen times maxLen. When the longest word is short, this is close to linear in n. When the dictionary has a very long word, the gain shrinks.

Step 3: a trie walks the dictionary letter by letter

The maxLen version still copies a substring and hashes it for every pair. A trie can remove that cost. A trie is a tree where each path from the root spells the start of some word. Each node can have up to 26 children, one for each letter a to z. A node is marked when a complete word ends there. Two words that share a start, like cat and cats, share their first three nodes.

Here is the trie for the five words. The root is the top. Marked nodes are shown with an asterisk.

root
 |- c - a - t*  - s*
 |- a - n - d*
 |- s - a - n - d*
 |- d - o - g*

The cat node is marked because cat is a word. The cats node is marked too, one step further. The and node is marked. The sand path starts at the root with s, which is a different branch from the cat branch.

Now the trie can replace the substring check. The new idea is this. Whenever ok[start] is true, the prefix before start can be split. So the next word can begin at start. Begin at the root of the trie and read the characters s[start], s[start + 1], and so on. Each character moves you one level deeper. If the node you reach is marked, then the piece from start to here is a word, so ok at the position just after this piece is true. If there is no child for the next character, stop. No word can start with those letters, so no longer walk can succeed.

Walk through catsanddog from position 0. ok[0] is true.

• Read c. The root has a child c. Move there.
• Read a. The c node has a child a. Move there.
• Read t. The ca node has a child t. Move there. This node is marked, so cat is a word, and ok[3] becomes true.
• Read s. The cat node has a child s. Move there. This node is marked, so cats is a word, and ok[4] becomes true.
• The next character is a. The cats node has no children, so stop.

From position 0 the walk read five characters, four of which matched. Next, the walk from position 3 is also needed, because ok[3] is now true. Read s, a, n, d. The sand node is marked, so ok[7] becomes true. The next character is d, and the sand node has no children, so stop.

The program then runs the same walk from every other start that is true. Positions 1 and 2 are skipped because ok[1] and ok[2] are false. The walk from position 4 reads a, n, d and marks and, so ok[7] is set again. The walk from position 7 reads d, o, g and marks dog, so ok[10] becomes true.

Notice what the walk never does. It never copies a substring. It never hashes a string. It moves through the trie one letter at a time. Each walk stops at the first letter that has no child, so it never goes past the longest word that begins with the same letters. That replaces the maxLen check with a stop that comes from the trie itself.

The code for the trie

The trie stores 26 child indexes per node, and -1 means no child. The class is small on purpose.

#include <array>
#include <string>
#include <vector>
 
// Words are lowercase letters a to z.
class Trie {
public:
    Trie() { nodes_.emplace_back(); }
 
    void insert(const std::string& word) {
        int cur = 0;
        for (char c : word) {
            const int k = c - 'a';
            if (nodes_[cur].next[k] == -1) {
                nodes_[cur].next[k] = static_cast<int>(nodes_.size());
                nodes_.emplace_back();
            }
            cur = nodes_[cur].next[k];
        }
        nodes_[cur].isWord = true;
    }
 
    int child(int node, int k) const { return nodes_[node].next[k]; }
    bool isWord(int node) const { return nodes_[node].isWord; }
 
private:
    struct Node {
        std::array<int, 26> next;
        bool isWord = false;
        Node() { next.fill(-1); }
    };
    std::vector<Node> nodes_;
};

The nodes live in a std::vector, and a node refers to its children by index, not by pointer. This matters for two reasons. The vector can grow and move its contents without breaking the links. And the code is simpler to read than a web of pointers.

Now the word break function that uses it.

std::pair<bool, std::size_t> wordBreakTrie(const std::string& s,
                                           const std::vector<std::string>& words) {
    Trie trie;
    for (const auto& w : words) trie.insert(w);
 
    const std::size_t n = s.size();
    std::vector<bool> ok(n + 1, false);
    ok[0] = true;
    std::size_t steps = 0;
    for (std::size_t start = 0; start < n; ++start) {
        if (!ok[start]) continue;
        int node = 0;
        for (std::size_t end = start; end < n; ++end) {
            const int k = s[end] - 'a';
            if (k < 0 || k >= 26) break;
            ++steps;
            node = trie.child(node, k);
            if (node == -1) break;
            if (trie.isWord(node)) ok[end + 1] = true;
        }
    }
    return {ok[n], steps};
}

The k < 0 || k >= 26 check handles a character that is not a lowercase letter. Such a character cannot be part of any word in this trie, so the walk stops there. The counter steps counts characters read, not lookups. It is a different unit from the lookups in the earlier versions, so the three numbers are not directly comparable. Use them to see the shape of the work, not as a speed test.

Running the trie version on the same inputs:

catsanddog: true (steps: 17)
catsandcat: true (steps: 17)
pineapple: false (steps: 1)

For pineapple the walk from position 0 reads p, and the root has no child p. Only one step is taken. The earlier versions did four or nine lookups for the same string, because they tested pieces that could never be words.

Checking the three versions agree

A faster method is only useful if it gives the same answers. Make a random test. Generate a dictionary of up to five words made of the letters a, b and c, with each word between 1 and 4 letters. Generate a string of up to 14 letters from the same set. Run all three functions and compare their answers. Repeat this 2,000 times with a fixed seed, so the same numbers come out each time.

The program prints this result:

random trials: 2000, mismatches: 0, answers yes: 249

Zero mismatches means the three versions agreed on all 2,000 inputs. The count of 249 yes answers shows the test had both yes and no cases. A test with only "no" answers would prove very little. Use a random test like this whenever you change a dynamic programming method, because the bugs in these methods are often one index off and show up only on some inputs.

Common mistakes

Forgetting the base case

If ok[0] is left false, every later entry depends on an earlier one that is false, so the whole table stays false. The function then answers no for every string, including the ones that should be yes. The base case is not an extra detail. It is the first true fact the rest of the table is built from.

A quick test catches this. Use the one-word dictionary {cat} and the string cat. The correct answer is yes. With ok[0] left false, the table is F F F F, and the answer is no. The output of a test shows the problem at once:

cat ok[0..3] = T F F T
cat ok[0..3] = F F F F

The second line is the broken version. The first line is correct.

Unsigned subtraction that wraps around

In C++ the type std::size_t is unsigned. It cannot hold a negative number. A subtraction that would go below zero does not give a negative result. It wraps around to a very large number. Take the version that starts the inner loop at i - maxLen with no guard. For the string a and the dictionary {a, abc}, the longest word has length 3. When i is 1, the expression i - maxLen is 1 - 3, which wraps to a huge number. The inner loop starts past its end, so it never runs. The answer is then no.

buggyLowest("a") = 0 (correct answer: 1)

The string a is a word in the dictionary, so the correct answer is 1, yes. The program printed 0, with no error message at all. This is the worst kind of bug, because nothing tells you that anything went wrong. The guard i > maxLen ? i - maxLen : 0 prevents it. Always check the order of a subtraction before you do it on an unsigned number.

Asking substr for a start past the end

std::string::substr(pos, count) throws an exception when pos is greater than the size of the string. A position equal to the size is allowed, and returns an empty string. A position greater than the size is not allowed. A mistake that adds 1 to a start index can push it past the end.

When the program runs a buggy version that asks for s.substr(i + 1, 1) on the string ab, with i equal to 2, the start is 3, which is past the size 2. The program stops with this message:

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::substr: __pos (which is 3) > this->size() (which is 2)

The message names the bad position and the size, so you can find the call. Read the number in the parentheses first. It tells you how far past the end the index went.

Scanning the dictionary as a list

Some programs store the dictionary in a std::vector and search it with a loop each time. That turns each check into a scan of every word. With 10,000 words, one check can compare against 10,000 strings. Use an unordered_set for the check, as in the examples here. Use the trie when the walk needs to stop early by prefix, as in step 3.

Assuming empty words are harmless

This lesson assumes every dictionary word has at least one letter. An empty word never matches here, because every piece has at least one letter, so it only adds clutter. If your input list can contain empty strings, remove them before building the set or the trie.

Practice

Exercise 1

Fill in the ok table by hand for the string pineapple, with the dictionary {pine, apple}. Give the table as true and false values from ok[0] to ok[9].

Show the answer

ok[0] is true. ok[1] to ok[3] are false, because p, pi and pin are not words. ok[4] is true, because pine is a word. For ok[5] to ok[8], the only true earlier entry is ok[4], and the pieces from it (a, ap, app, appl) are not words, so these are false. ok[9] is true, because ok[4] is true and the piece from position 4 to 9 is apple. So the table is T F F F T F F F F T, and the answer is yes. This matches the program output for pineapple in the lesson.

Exercise 2

The dictionary is {a, abc}, so maxLen is 3. Which is the smallest j you must try when computing ok[5] in a string of length at least 5?

Show the answer

The smallest j is 2, because 5 - 3 is 2. A piece that ends at 5 and is a word can be at most 3 letters long, so it starts at position 2 or later. Any earlier j would make a piece longer than 3 letters, and no word in this dictionary is that long.

Exercise 3

Walk the trie by hand for s = "cats" and the dictionary {cat, cats, dog}, starting at position 0. How many character steps does the walk take, and which entries of ok become true?

Show the answer

The walk reads c, a, t and then s, which is 4 character steps. The node after t is marked, so ok[3] becomes true. The node after s is marked, so ok[4] becomes true. The walk then stops because the node for cats has no children and the string has no more characters. The entries ok[3] and ok[4] are true, and the answer for the whole string is ok[4], which is yes.

Exercise 4

In wordBreakMaxLen, suppose you add a check that returns early when ok[n] becomes true. Does the answer change? Explain why or why not.

Show the answer

The answer does not change. Each ok[i] only depends on entries with smaller indexes, so once ok[n] is true its value cannot change again. Returning early only skips later work. The lookup count goes down, but the function still returns the same yes answer.

Exercise 5

A string has 10,000 characters and the longest word has 20 letters. In the worst case, about how many substring checks does wordBreakMaxLen make? Give a rough number.

Show the answer

For each of the 10,000 values of i, the inner loop tries at most 20 starts. So the number of checks is at most about 10,000 times 20, which is 200,000. The wordBreakAllSplits version could try up to about 10,000 starts for each i, which is about 50 million pairs in the worst case, so the gain is large for this input.

Summary

• A table ok records, for each prefix, whether it can be split into dictionary words. The answer is ok[n].
• The base case ok[0] is true, and each later entry looks back only to earlier entries.
• Limiting the start of each piece to maxLen characters back avoids checks that cannot succeed.
• A trie walks the dictionary one letter at a time and stops when no word can continue, so it never copies or hashes substrings.
• Check a new version against the simple one on many random inputs before you trust it.