Prefix segmentation DP

43 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You are given the letters leetcode and a small dictionary, leet and code, and asked whether the string can be cut into dictionary words with nothing left over. By hand you would try a first cut: is l a word? No. le? No. lee? No. leet? Yes, so now solve the rest, code, the same way.

That looks harmless, but the "solve the rest" part can repeat itself. Imagine the dictionary a, aa, aaa and the string aaaaaaaab. The first cut can be after 1, 2 or 3 letters; each of those leaves a string that can again be cut three ways. The number of attempts grows like 3 × 3 × 3 × … and for 30 letters it is in the billions, and every attempt eventually hits the b and fails. Worse, most attempts re-solve the same leftover: "can aaaab be cut?" is asked thousands of times.

Build the structure, one piece at a time

The repeated question has only n + 1 different forms: can the first i letters be cut cleanly, for i from 0 to n. So keep one answer per prefix in an array dp of n + 1 cells. Start with everything unknown except dp[0], which is true: the empty prefix needs no words.

Fill the cells left to right. To decide dp[i], look at every earlier position j that is already true and ask whether the letters between j and i form a dictionary word. One yes is enough.

The last cell, dp[8], is true, so the whole string can be cut: leet + code. Notice the structure is just an array of yes/no answers, filled once, and each new answer is built only from earlier answers.

Why it is correct

The invariant: dp[i] is true exactly when the first i letters can be split into dictionary words. Suppose it holds for every index below i. Any valid split of the first i letters has a last word; say it starts at j. Then the letters before j are also validly split, so dp[j] is true, and s[j:i] is a word. Our loop checks exactly that pair, so it finds the split. In the other direction, if the loop sets dp[i] true, it has a true dp[j] plus one more word, which is a valid split. So the invariant survives each step, and dp[n] answers the question.

dp[i] = OR over j < i of ( dp[j] and s[j:i] ∈ dictionary )

Why it is fast

There are n cells. Cell i looks back at up to i earlier cells, so the total number of (j, i) pairs is 1 + 2 + … + n = n(n+1)/2, which is O(n²). Each pair costs one dictionary lookup, constant time with a hash set (or O(word length) with a trie). For 30 letters that is about 465 lookups instead of billions of attempts. The only memory is the n + 1 booleans. A small extra: if the longest dictionary word has L letters, j only needs to go back L positions, giving O(n · L).

How to recognise it in an interview

Cues: "can the string be split into", "segment", "decode", "how many ways to break". Any time a prefix's answer depends only on shorter prefixes plus a last piece, this array is the tool. Say: I will keep one answer per prefix and build each from earlier prefixes. Word Break is this exactly. Word Break II stores, for each prefix, the list of splits instead of a boolean. Decode Ways is the same loop where the "words" are one- or two-digit codes and the cells hold counts instead of true or false.

02The idea in one line

dp[i] is true if some j < i has dp[j] true and s[j:i] in the dictionary.

Reach for it when: Word break I/II, concatenated words, decode ways, minimum extra characters.

Cost: O(n² ) time.

03The walk-through, step by step

The video works one example: Word Break 'leetcode' with [leet, code]. These are its captions in order, so you can follow without the video or check a step you missed.

1. dp[0] is true; dp[i] is true if some dp[j] is true and s[j:i] is a word
2. i = 2: from dp[0] ✓, s[0:2] = 'le' is not a word → dp[2] stays ·
3. i = 4: dp[0] ✓ and s[0:4] = 'leet' is a word → dp[4] = ✓
4. i = 5: from dp[4] ✓, s[4:5] = 'c' is not a word → dp[5] stays ·
5. i = 7: from dp[4] ✓, s[4:7] = 'cod' is not a word → dp[7] stays ·
6. i = 8: dp[4] ✓ and s[4:8] = 'code' is a word → dp[8] = ✓
7. dp[8] is ✓: 'leet' + 'code' → true
8. Each i tries every j: O(n²) with a word set (O(n·L) with a trie)

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).