The idea: jumps from word to word
You get a string s with no spaces, such as leetcode, and a dictionary of words, such as {leet, code}. Can s be split into a sequence of dictionary words? A word may be used any number of times. This is the word break problem.
Number the gaps between the letters: boundary 0 is before the first letter and boundary n is after the last. A dictionary word that starts at boundary j and ends at boundary i is a jump from j to i. The string splits into words exactly when a chain of jumps leads from 0 to n. The page draws each jump as an arc over the letters.
The recurrence
Let dp[i] be true when the first i letters, s[0..i), split into words. The empty prefix needs no words, so dp[0] = true. For a longer prefix, look at its last word: it is some s[j..i), and what comes before it, s[0..j), must split too.
dp[0] = true dp[i] = true if some j < i has dp[j] = true and s[j..i) in the dictionary
Fill dp[1], dp[2], … left to right; the answer is dp[n]. Only the boundaries j with dp[j] true are worth testing, so the animation colours those cells blue and lists each substring it tests with ✓ or ✗. A second cut: no word is longer than the longest dictionary word L, so only j ≥ i − L can match. (Demo: leetcode with {leet, code}; Demo: applepenapple uses apple twice.)
Why taking the first word that fits fails
A greedy split takes a word as soon as one matches and moves on. On catsandog with {cats, dog, sand, and, cat}, greedy might take cat, then sand, and be stuck on "og". Taking cats, then and, is stuck on "og" too. The DP tries every split at once: it finds that boundaries 0, 3, 4 and 7 are reachable, but no word runs from a reachable boundary to boundary 9, so dp[9] is false (Demo: catsandog cannot be split). Add one letter, catsanddog, and both cats and dog and cat sand dog work (Demo: catsanddog, 2 ways).
Counting the segmentations
The same jumps also count the splits. Let ways[i] be the number of ways to split s[0..i). Every split of the prefix ending at j continues with the word s[j..i), so
ways[0] = 1 ways[i] = sum of ways[j] over every j with s[j..i) in the dictionary
dp[i] is just ways[i] > 0. On pineapplepenapple with {apple, pen, applepen, pine, pineapple}, boundary 9 is reached two ways (pine apple, pineapple) and boundary 12 three ways (two through pen, one through applepen), so ways[17] = 3 (Demo: pineapplepenapple, 3 ways).
The count can grow very fast while the DP stays small. With {a, aa, aaa}, ways[i] = ways[i−1] + ways[i−2] + ways[i−3], the tribonacci numbers: 44 ways for seven a's, over 35,000 for eighteen (Demo: aaaaaaa with {a, aa, aaa}, 44 ways). Listing every split (the "Word Break II" problem) therefore takes exponential time in the worst case, but deciding or counting takes only the table.
Finding one split
While filling the table, remember for each boundary i the starts j of the words that end there. If dp[n] is true, walk back from n: take one recorded jump, note its word, continue from its start, and stop at 0. Read backwards, the words are a split of s. The animation takes the jump with the smallest j each time and colours the path green.
Running time
| Version | Substring tests | Note |
|---|---|---|
| Every j < i | O(n²) | each test hashes a substring of up to n letters |
| Only j ≥ i − L | O(n L) | what the page does, also skipping false dp[j] |
| Plain recursion, no table | exponential | the same prefix is re-split many times |
A trie of the dictionary, or matching the words with Aho-Corasick, finds all words starting at a boundary in one scan instead of hashing each substring. For other one-dimensional tables with a trace back, see Longest Increasing Subsequence and Coin Change, which counts ways the same way ways[i] does; for two strings, see Edit Distance and Longest Common Subsequence.
What the page leaves out
Listing every segmentation (Word Break II) beyond the first few; top-down memoized recursion, which fills the same table on demand; tries and Aho-Corasick for fast word lookup; choosing the most likely split by word frequencies, as real text segmenters for Chinese or for URLs and hashtags do; and very long strings, where the dictionary lookup cost dominates.
See where this page fits on the Dynamic Programming mind map.