Word Break Problem, in depth: reachability DP, measured recursion blow-up, trie matching, counting, listing and Viterbi segmentation

The model: reachability over positions

Number the gaps between characters 0 to n, where n is the string length. Position i is reachable if the prefix s[0:i] can be fully segmented. Position 0 is reachable (the empty prefix). Position i is reachable if some earlier reachable position j has s[j:i] in the dictionary. The answer is whether n is reachable. Seen this way, word break is reachability in a directed acyclic graph. The nodes are positions, and each dictionary word occurring at j and ending at i is an edge j to i. Every algorithm below is a way of exploring that graph without enumerating paths.

Why naive recursion explodes

The direct recursion tries every word that prefixes the string and recurses on the rest. It is correct, and exponential when the answer is no. The standard bad case is "aaa...ab" with dictionary {a, aa, aaa}. Every split of the a's is explored, and each one fails only at the final b. Measured call counts:

Each extra four characters multiplies the work by about 11.5. That is the tribonacci growth rate (about 1.84 per character), because the number of ways to write n as 1s, 2s and 3s grows that fast. The fix is to notice that the recursion only ever asks n + 1 distinct questions, one per suffix start, and to answer each once.

The bottom-up DP with a length bound

Bottom-up, fill a boolean array ok[0..n] left to right. One refinement matters in practice. A word ending at i starts at least i − L, where L is the longest dictionary word, so only L candidate starts need checking:

def word_break(s, words):
    D = set(words)
    if not D:
        return s == ""
    L = max(map(len, D))
    n = len(s)
    ok = [False] * (n + 1)
    ok[0] = True
    for i in range(1, n + 1):
        for j in range(i - 1, max(0, i - L) - 1, -1):    # nearest start first
            if ok[j] and s[j:i] in D:
                ok[i] = True
                break
    return ok[n]

Without the bound, the inner loop scans j from 0, so the work is O(n²) substring lookups. Each lookup hashes a slice of length up to n, so the true cost is closer to O(n³) character operations. With the bound it is O(n · L) lookups of slices of length at most L, so O(n · L²) character work, linear in n. On "a"×5000 + "b", the unbounded loop did 10,001 dictionary checks and the bounded one 5,003. The checks are few because the early break fires quickly. The real saving is that the unbounded version, at the final b, hashed slices of every length up to 5,000, and the bounded one never hashes more than 3 characters at a time.

Top-down memoization gives the same complexity and can skip unreachable suffixes, but in Python it recurses n deep. The default limit of 1,000 frames fails on any long input. Prefer the iterative form for production. On the worked example "catsandog", ok comes out true at positions 0, 3, 4 and 7 (after cat, cats, and sand or and) and false at 9, so the answer is no. The "og" tail matches nothing.

Trie and Aho-Corasick matching

The set-lookup DP hashes up to L slices per position. A trie turns that inside out. From each reachable j, walk the trie along s[j], s[j+1] and so on, marking ok[i] wherever a word ends. Stop as soon as the trie has no child. Each character step is O(1), so the total work is O(n · L) character steps in the worst case. It is usually far less, because most walks die after a character or two.

def word_break_trie(s, root):           # root: dict-of-dicts trie, "$" marks a word end
    n = len(s)
    ok = [False] * (n + 1)
    ok[0] = True
    for j in range(n):
        if not ok[j]:
            continue                    # only extend from reachable positions
        node = root
        for i in range(j, n):
            node = node.get(s[i])
            if node is None:
                break
            if "$" in node:
                ok[i + 1] = True
    return ok[n]

For very large dictionaries scanned over long text, Aho-Corasick reports every dictionary occurrence in one left-to-right pass in O(n + matches). Each match (start, end) is an edge in the position graph, and reachability is a single sweep over edges sorted by end. That is the right shape for streaming input, or when the same text is checked against several dictionaries.

Counting and listing segmentations

Replace the boolean with a count to get the number of segmentations: c[i] is the sum of c[j] over words s[j:i]. Counts grow fast. "a"×30 with {a, aa} has 1,346,269 segmentations, the 31st Fibonacci number. With {a, aa, aaa} it has 53,798,080. "a"×60 with {a, aa} has 2,504,730,781,961. Use big integers, or reduce modulo a prime if the caller only needs the count mod p.

Listing all segmentations (Word Break II) has output that can be exponential, so no algorithm is polynomial in n alone. What you can avoid is wasted work on dead branches. Compute reachability backwards first: good[i] is true when the suffix from i can be segmented. Then only descend into words that land on a good position, and every branch explored produces at least one output.

def all_segmentations(s, words):
    D, n = set(words), len(s)
    L = max(map(len, D))
    good = [False] * (n + 1)
    good[n] = True
    for i in range(n - 1, -1, -1):                     # suffix reachability
        good[i] = any(good[j] and s[i:j] in D for j in range(i + 1, min(n, i + L) + 1))
    out, path = [], []
    def go(i):
        if i == n:
            out.append(" ".join(path))
            return
        for j in range(i + 1, min(n, i + L) + 1):
            if good[j] and s[i:j] in D:                # never enter a dead suffix
                path.append(s[i:j]); go(j); path.pop()
    if good[0]:
        go(0)
    return out

For "catsanddog" this returns "cat sand dog" and "cats and dog". For "pineapplepenapple" with {apple, pen, applepen, pine, pineapple} it returns three: "pine apple pen apple", "pine applepen apple" and "pineapple pen apple". Without the good array, the "aaa...ab" input would explore exponentially many branches to print nothing.

Choosing the best segmentation

Real text is ambiguous, and "is there a segmentation" is the wrong question. To show this, a 15-word toy dictionary (there, the, re, is, no, noon, on, one, e, eh, ere, here, her, his, ne) admits 20 segmentations of "thereisnoonehere". They range from "there is no one here" to "the re is noon eh ere". The practical fix is to score segmentations and pick the best. A unigram model assigns each word w a probability P(w) from corpus counts and scores a segmentation by the sum of log P(w). Maximizing it is the same DP with max instead of or. This is the Viterbi algorithm on the position graph:

import math

def segment(s, counts):
    total = sum(counts.values())
    L, n = max(map(len, counts)), len(s)
    best = [-math.inf] * (n + 1)
    back = [0] * (n + 1)
    best[0] = 0.0
    for i in range(1, n + 1):
        for j in range(max(0, i - L), i):
            w = s[j:i]
            if w in counts and best[j] > -math.inf:
                score = best[j] + math.log(counts[w] / total)
                if score > best[i]:
                    best[i], back[i] = score, j
    if best[n] == -math.inf:
        return None                     # no segmentation at all
    words, i = [], n
    while i > 0:
        words.append(s[back[i]:i])
        i = back[i]
    return words[::-1]

With made-up counts that give common words high frequency (the 1,000, is 900, there 600, noon 30, eh 5), it returns "there is no one here" with log-score −11.31. Because the score is a sum of negative terms, the model naturally prefers fewer, more common words. In production, the counts come from a real corpus. You add a penalty-scored fallback for unknown words, often length-dependent, so a single unseen name does not make the whole string unsegmentable. Bigram models improve accuracy by conditioning each word on the previous one, at the cost of a DP state per (position, previous word).

Failure modes

• Exponential recursion on no-instances. Memoize or go bottom-up. Test with "a"×40 + "b", not only with examples that succeed.
• Recursion depth. Memoized top-down code recurses once per character and dies on long inputs in languages with small stacks. Iterate.
• Empty string in the dictionary. An empty word is an edge from i to itself. Naive recursion loops forever, and L may be computed as 0. Filter it out at load time.
• One huge dictionary word. L is the maximum length, so a single 500-character entry makes every position try 500 starts. The trie version does not care, which is one more reason to use it.
• Unicode. Slicing by code units can split a character, and dictionaries and input may disagree on normalization (precomposed versus combining accents) or case. Normalize both to the same form (for example NFC plus case folding) before matching.
• Exploding output. An API that returns all segmentations can be asked for billions. Cap the count, stream results, or return the count and the best one.

Trade-offs

For a one-off check against a small dictionary, the bounded set-lookup DP is about ten lines and fast enough. For many queries against a fixed dictionary, build a trie once and reuse it. For long streams, or many dictionaries, use Aho-Corasick and a sweep. If the output feeds anything user-visible, the decision problem is not enough. Use a scored DP, and spend your effort on the frequency table and the unknown-word penalty, not the algorithm. If you are new to the recurrence style, the dynamic programming overview and the animated DP introduction walk through the same fill-a-table pattern on simpler problems.

What to do next

1. Implement the bounded bottom-up DP and test it on "applepenapple", "catsandog" and "a"×40 + "b"; the last must return instantly.
2. Add a back-pointer array and reconstruct one segmentation, then switch the boolean to a count and check "a"×30 with {a, aa} gives 1,346,269.
3. Replace set lookups with a trie walk and compare timings on a 100,000-word dictionary.
4. Implement listing with the backward good array and confirm it explores no dead branches on "aaa...ab".
5. Build a unigram segmenter from real word counts, add an unknown-word penalty, and evaluate it on hashtags or domain names you have ground truth for.
6. Normalize Unicode and case on both the dictionary and the input before any of this reaches production.