Medium Problemsstringcountinglinear

Word Break Problem

Given a string and a dictionary of words, decide whether the string can be split into a sequence of one or more dictionary words with no leftover characters.

Do this lesson first: coin change

Example input

s = "catsandog", dictionary = {cat, cats, and, sand, dog}

Expected output

0 (no valid split)

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

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

Ask where the last word of the split begins. If the first i characters split legally, some word ends exactly at i, and that word starts at some j. Then s[j..i) has to be in the dictionary and everything before j has to split legally on its own, which is dp[j]. Try every j whose suffix is a dictionary word and take an or over them. Only j whose s[j..i) is actually a word are worth reading at all, and for many i there are none.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = true, the empty prefix, which splits vacuously into no words at all. That base is what lets any single dictionary word starting at position 0 turn its cell on. Fill left to right, since every j is smaller than i. Several cells here read nothing whatsoever, because no suffix ending at them is a dictionary word; those are 0 by default rather than by comparison.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

1

0

1

0

1

0

word-break.ts

1function wordBreak(s, dict) {
2 const n = s.length;
3 const dp = [true];
4 for (let i = 1; i <= n; i++) {
5 dp[i] = false;
6 for (let j = 0; j < i; j++) {
7 if (dict.has(s.slice(j, i)) && dp[j]) {
8 dp[i] = true;
9 break;
10 }
11 }
12 }
13 return dp[n];
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

word-break.ts

1function wordBreak(s, dict) {
2 const n = s.length;
3 const dp = [true];
4 for (let i = 1; i <= n; i++) {
5 dp[i] = false;
6 for (let j = 0; j < i; j++) {
7 if (dict.has(s.slice(j, i)) && dp[j]) {
8 dp[i] = true;
9 break;
10 }
11 }
12 }
13 return dp[n];
14}

Where people go wrong

Stopping at the first prefix that splits and calling the whole string splittable. On this input the first seven characters split two different ways and the string still fails. The greedy cousin of the same mistake is committing to the longest dictionary word that matches at each position: take "cats" here and you strand "andog"; only backing up to "cat" gets you as far as index 7, and the table tries both without you having to notice.

Return the number of ways to split the string rather than whether it can be split.
The or becomes a sum and the base becomes 1. Same cells, same reads, same order; only the operator over the candidates changes, which is the clearest illustration in this whole tier that the state is the hard part and the operator is not.
Return one actual split, not just whether one exists.
Store the winning j alongside each true cell and walk backwards from n. That is reconstruction, and it costs one extra array, not an extra dimension.

Unbounded Knapsack Tile Stacking Problem