Word Break Problem: Dynamic Programming Over Cut Points

Word break asks whether a string can be chopped into dictionary words. It sounds like a string problem, and the first instinct is to scan left to right, peeling off words as you find them. That instinct is wrong in a way that is worth understanding, because the fix — a table with one yes-or-no per prefix — is the cleanest introduction to dynamic programming over positions in a string.

The problem it solves

Given a string s and a list of words, can s be split into a sequence of those words, each used any number of times? codecamp with the words code, camp and cam can: code + camp. catsandog with cats, dog, sand, and and cat cannot.

The same question appears when segmenting text written without spaces, when tokenising against a fixed vocabulary, or when checking whether an identifier is built only from known parts.

The intuition

Greedy fails. Taking the longest word available at each step looks sensible, but a long early word can strand the rest. With words a, aa and aab, greedy reads aaab as aa and is left with ab, which splits no further. The valid split, a + aab, needed a shorter first word.

Plain recursion is correct but slow. Try every word that fits at the front, recurse on the rest. It explores every way of splitting, and on inputs with many overlapping choices that number grows exponentially — the same suffixes get asked about again and again.

The table stores the answer for each prefix once. Let ok[i] mean "the first i characters can be split into words". Then:

• ok[0] is true: the empty prefix is split into zero words.
• ok[i] is true if there is some cut point j before i where ok[j] is true and s[j:i] is a word. The prefix up to the cut splits by itself, and the piece after the cut is one more word.

The final answer is ok[len(s)]. Each cell depends only on cells to its left, so filling left to right works.

Two refinements matter in practice. The last word cannot be longer than the longest dictionary word, so j only needs to go back that far. And if you record which j made each cell true, you can walk those cuts back from the end to recover the actual words.

Watch it run

The table for codecamp has nine cells, from the empty prefix to the whole word. Cell 4 turns true because code is a word. Cell 7 turns true too, because cam is a word — and then leads nowhere, since the remaining p is not. Cell 8 is true through the cut at 4, not the one at 7. That dead end at cell 7 is the reason every cut is tried rather than committing to the first word that fits.

The code

The table with cut tracking and reconstruction, plus the greedy version for comparison:

def word_break(s, words):
    words = set(words)
    longest = max(map(len, words), default=0)
    ok = [True] + [False] * len(s)              # ok[i]: s[:i] splits into words
    cut = [None] * (len(s) + 1)                 # where the last word of s[:i] starts
    for i in range(1, len(s) + 1):
        for j in range(max(0, i - longest), i): # the last word can't be longer
            if ok[j] and s[j:i] in words:
                ok[i], cut[i] = True, j
                break
    if not ok[-1]:
        return None
    parts, i = [], len(s)
    while i:                                    # walk the cuts back from the end
        parts.append(s[cut[i]:i])
        i = cut[i]
    return parts[::-1]

def greedy_longest(s, words):                   # take the longest word each time
    parts, i = [], 0
    while i < len(s):
        for j in range(len(s), i, -1):
            if s[i:j] in words:
                parts.append(s[i:j]); i = j
                break
        else:
            return None
    return parts

print(word_break("codecamp", ["code", "camp", "cam"]))      # ['code', 'camp']
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))   # None
print(word_break("pineapple", ["apple", "pine", "pineapple", "pen"]))   # ['pineapple']
words = ["a", "aa", "aab"]
print(greedy_longest("aaab", words), word_break("aaab", words))   # None ['a', 'aab']

The inner loop breaks at the first working cut, which is enough to answer yes or no and to recover one valid split. Returning all splits is a different problem whose output can itself be exponential in size.

The brute force here is the plain recursion. First, how badly it scales on a string that can never be split — a run of as ending in b:

import random

calls = 0
def splits_naive(s, words):                     # try every first word, recurse, no memo
    global calls
    calls += 1
    if not s:
        return True
    return any(s.startswith(w) and splits_naive(s[len(w):], words) for w in words)

counts = []
for n in (10, 15, 20):                          # a run of a's that can never end well
    calls = 0
    splits_naive("a" * n + "b", ["a", "aa", "aaa"])
    counts.append(calls)
print(counts)                                   # [600, 12640, 266079]

random.seed(2)
ok = True
for _ in range(3000):
    words = list({"".join(random.choice("ab") for _ in range(random.randint(1, 3)))
                  for _ in range(random.randint(1, 4))})
    s = "".join(random.choice("ab") for _ in range(random.randint(0, 12)))
    parts = word_break(s, words)
    ok &= (parts is not None) == splits_naive(s, words)
    ok &= parts is None or ("".join(parts) == s and all(p in words for p in parts))
print(ok)                                       # True

Five more as multiply the work by roughly twenty. The table on the same 21-character input fills 22 cells. On small random inputs, both agree on every yes-or-no answer, and every split the table returns really does join back into s using only dictionary words.

The complexity

There are n + 1 cells. Each tries at most L cut points, where L is the longest word length, and each try slices and hashes a piece of length up to L. That is O(n × L²) time. Without the length bound, j runs back over every earlier cell and the slices can be as long as s, which makes it O(n³). Memory is O(n) for the table plus the dictionary set.

With a trie instead of a hash set, you can walk forward from each true cell one character at a time and stop as soon as no word continues, which avoids re-hashing overlapping slices.

Where it goes wrong

• Committing greedily. Shortest-first and longest-first both have counterexamples. The table tries every cut.
• Forgetting ok[0]. Without the true base case nothing can ever become true, and every string is reported as unsplittable.
• Checking the word but not the prefix. s[j:i] in words alone ignores whether s[:j] splits. Both halves of the condition are required.
• Memoising the wrong key. Top-down versions must cache by position, not by the remaining string built with slicing, or the cache lookups themselves cost O(n) each.

For the prefix structure mentioned above, see trie basics.

How to say it in an interview

"Let ok[i] be whether the first i characters split into words, with ok[0] true. For each i, I look for a cut j where ok[j] holds and s[j:i] is in the dictionary, only going back as far as the longest word. The answer is ok[n]. That's O(n × L) checks. Greedy doesn't work — aaab with a, aa, aab is a counterexample — and plain recursion repeats the same suffixes exponentially."

If asked for the words themselves, mention the cut array before writing it. Recording one index per cell is all it takes, and it shows you are thinking about the answer the caller actually needs.