Word Break

Dynamic programming · Mark reachable string boundaries · Stretch · about 30 min

Why it matters

It is the key mental move behind many segmentation and string DP questions.

How it connects

A grid cell represented a reachable location. Here an index represents a reachable split in a string.

Try first

What should dp[i] mean about the first i characters?

Interview cue

Each true DP index is a valid word boundary that can seed a later boundary.