Word Break: Segmenting Strings with 1D Dynamic Programming
Solve Word Break with dynamic programming — memoized recursion and a bottom-up 1D DP table, with a worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Word Break looks like a string puzzle and turns out to be a dynamic programming problem in disguise. The question — can this string be cut into a sequence of dictionary words? — hides a nasty trap: the number of ways to place the cuts grows exponentially, so a naive recursion re-solves the same suffix thousands of times.
The fix is the defining move of 1D dynamic programming: remember the answer for each substring the first time you compute it, and never compute it twice. Do that and an exponential search collapses into a clean O(n²) scan.
Master this one and the same shape reappears everywhere — Word Break II, palindrome partitioning, and any "can I chop this input into valid pieces?" question.
The problem
Given a string s and a list of words wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same dictionary word may be reused any number of times.
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true // "leet" + "code"
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false // no cut sequence consumes the whole stringThe second example is the one that punishes brute force. You can match "cats" then "and", but you're left with "og", which is not a word — and there are several near-misses like this to explore before you're sure the answer is false.
The brute force baseline
The direct recursion asks: for the remaining string remS, is there a dictionary word that forms a prefix, such that the rest is also segmentable?
function wordBreak(s, wordDict) {
const fn = (remS) => {
if (remS === "") return true; // consumed everything
for (let i = 0; i < remS.length; i++) {
const substr = remS.substring(0, i + 1);
if (wordDict.includes(substr) && fn(remS.substring(i + 1))) {
return true;
}
}
return false;
};
return fn(s);
}This is correct but exponential. Consider s = "aaaaaaa" with wordDict = ["aaa", "aaaa"]. From the front you can peel "aaa" or "aaaa", and each choice lands you on a shorter all-a suffix that branches again the same way. The suffix "aaa" gets reached through many different cut paths, and each time the recursion re-explores it from scratch. That repeated work is O(2ⁿ) in the worst case.
The key insight: memoize on the remaining string
Two different cut paths that consume different prefixes can leave you staring at the exact same suffix. Whether "og" is breakable does not depend on how you got there — it is a property of the string "og" alone. That is the textbook signature of overlapping subproblems, and it means the answer for each distinct suffix is worth caching.
So key a memo by the remaining string. The first time you resolve fn(remS), store the boolean under remS. Every later visit is an O(1) lookup instead of a re-exploded subtree.
Caching the false results matters just as much as caching the true ones. In catsandog, memoizing that "og" is unbreakable is exactly what stops the search from re-descending into that dead end over and over.
The optimal solution
Two implementations. The top-down version is the brute force above with a dp cache bolted on — minimal change, maximum speedup:
var wordBreak = function(s, wordDict) {
let dp = {};
let fn = (remS) => {
if (remS === "") return true;
if (remS in dp) return dp[remS];
let res = false;
for (let i = 0; i < remS.length; i++) {
let substr = remS.substring(0, i + 1);
if (wordDict.includes(substr) && fn(remS.substring(i + 1))) {
res = true;
}
}
return dp[remS] = res;
};
return fn(s);
};The bottom-up version turns the recursion inside out. Let dp[i] mean "the first i characters of s can be segmented." dp[0] is true (the empty prefix is trivially segmentable), and each dp[i] is built from earlier entries you already know:
var wordBreak = function(s, wordDict) {
const wordSet = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
};The recurrence is dp[i] = OR over j of (dp[j] AND s[j..i] ∈ dict). In words: prefix s[0..i] is breakable if there's some split point j where the front s[0..j] was already breakable and the piece s[j..i] is a dictionary word. Swapping wordDict.includes (an O(k) array scan) for a Set makes each membership check O(1) on average.
Walkthrough
Trace the bottom-up table on s = "leetcode", wordDict = ["leet", "code"]. The array dp has length 9 (indices 0–8). dp[0] = true is the seed; every other cell starts false.
| i | prefix s[0..i] | winning split j | piece s[j..i] | dp[j] | in dict? | dp[i] |
|---|---|---|---|---|---|---|
| 1 | l | — (no j works) | — | — | — | false |
| 2 | le | — | — | — | — | false |
| 3 | lee | — | — | — | — | false |
| 4 | leet | 0 | leet | true | yes | true |
| 5 | leetc | — (only dp[4] is true, but c ∉ dict) | — | — | — | false |
| 6 | leetco | — | — | — | — | false |
| 7 | leetcod | — | — | — | — | false |
| 8 | leetcode | 4 | code | true | yes | true |
The two live cells are dp[4] and dp[8]. At i = 4 the split j = 0 matches "leet" off the dp[0] anchor. Then at i = 8 the only split worth trying is j = 4, because dp[4] is the sole earlier true cell — and s[4..8] is "code", which is in the dictionary. The final answer is dp[8] = true, and the two true cells reconstruct the segmentation "leet" + "code".
Notice how sparse the table is: most prefixes are dead (false), and the inner loop skips them instantly because dp[j] is false before it even looks at the dictionary.
Complexity
For a string of length n with dictionary words up to length m:
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute-force recursion | O(2ⁿ) | O(n) | every suffix re-explored across many cut paths |
| Top-down memoized | O(n²·m) | O(n²) | n suffixes × n prefix splits × substring/lookup cost |
| Bottom-up 1D DP | O(n²) | O(n) | two nested loops over indices; a Set gives O(1) lookups |
The bottom-up table is the tightest: i runs to n and j runs to i, so O(n²) split attempts, each doing an O(1) average-case Set lookup (treating substring extraction as amortized). Space is a single array of n + 1 booleans, O(n).
Common mistakes
- Forgetting the
dp[0] = trueanchor. Without it, no prefix can ever match its first word, and every cell staysfalse. The empty prefix being "breakable" is what lets the first real dictionary hit propagate. - Keeping
wordDictas an array.wordDict.includes(...)is an O(k) linear scan run inside two nested loops. Convert to aSetonce up front so membership is O(1). - Skipping memoization in the recursive version. Plain recursion is correct but times out on adversarial inputs like
"aaaaaaa"with["aaa","aaaa"]. Thedpcache is the whole point. - Not caching
falseresults. Caching only the successes still lets dead suffixes such as"og"get re-searched. Store every resolved suffix,trueorfalse. - Returning after the first
truecut instead of confirming the whole string. A prefix matching a word does not mean the entire string breaks — you must reachdp[s.length](orremS === "").
Where this pattern shows up next
The "build the answer for length i from smaller lengths you already solved" recurrence is the backbone of 1D DP:
- Fibonacci Number — the simplest possible version of "each state is a combination of earlier states."
- Climbing Stairs — same forward recurrence, counting paths instead of testing feasibility.
- Min Cost Climbing Stairs — the recurrence carries an accumulated cost, so you minimize instead of OR.
- House Robber — a take-it-or-skip-it choice at each index, still resolved left to right.
You can also step through Word Break interactively to watch the recursion tree memoize and the DP table fill in, one cell at a time.
FAQ
Why is Word Break a dynamic programming problem and not just recursion?
Because the recursion visits the same suffix through many different cut paths, and each visit would re-solve it from scratch — that's exponential overlapping work. Dynamic programming caches the answer for each distinct substring the first time it's computed, so every repeat is an O(1) lookup. That single change drops the running time from O(2ⁿ) to O(n²).
What is the time and space complexity of the optimal Word Break solution?
The bottom-up 1D DP solution runs in O(n²) time and O(n) space, where n is the length of s. The outer loop picks a prefix length and the inner loop tries every split point, giving n² split attempts, each an O(1) average-case Set membership check. Space is one boolean array of size n + 1.
Should I use top-down memoization or bottom-up DP?
Both are O(n²) and both are accepted. Top-down memoization is closer to the natural recursive idea — write the brute force, add a dp cache keyed by the remaining string, done — so it's easier to derive under pressure. Bottom-up fills a flat array with no call-stack overhead and no recursion-depth risk, which is why it's the more common "clean" answer. Pick whichever you can write bug-free.
Why does dp[0] have to be true?
dp[i] means "the first i characters can be segmented," so dp[0] asks whether the empty prefix is segmentable — and it is, using zero words. That base case is the anchor the whole table grows from: when the inner loop checks dp[j] && wordSet.has(s.substring(j, i)), the very first dictionary word can only register a hit because dp[0] was already true.
How would I return the actual words, not just true or false?
Solve the boolean version first, then reconstruct: walk backward from dp[s.length], and at each position find a split j where dp[j] is true and s[j..end] is a dictionary word, recording that word and jumping to j. To return every possible segmentation (that's the Word Break II problem), you instead recurse with memoization that stores the list of sentences for each suffix rather than a single boolean.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.