Word Break
A prefix is breakable if some split point is breakable and the remainder is a word.
End-to-end prefix DP trace
Problem
Given a string and a collection of allowed words, decide whether the entire string can be split into one or more dictionary words. Each dictionary word may be used repeatedly, and the pieces must appear consecutively without leftover characters.
Examples
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
The Goal
Decide whether s splits into dictionary words with nothing left over. Words can repeat.
You don't need the split itself, only whether one exists. Work along the string and remember which prefixes can be split. If the whole string is one of them, the answer is true.
For applepenapple, the prefixes apple and applepen can be split, and the last apple finishes the string.
Goal: reach the end
Find a chain of words whose boundaries start at index 0 and end at index n. Each word starts where the last one ended.
Prefix DP
Let dp[i] say whether the first i characters, s[0:i], can be split. The empty prefix can, so dp[0] = true.
dp[i] is true if some earlier boundary j has dp[j] true and s[j:i] is a word.
For i = 8, take j = 5: dp[5] is true and s[5:8] is pen, so dp[8] is true.
Try each earlier j: dp[j] must be true and s[j:i] a word.
dp[5] plus "pen" makes dp[8] true.
The Algorithm
Fill dp left to right. For each i, try every earlier j, and stop at the first split that works, because one is enough.
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]Include j = 0. That's where the first word starts.
| Approach | Correct? | Why |
|---|---|---|
| Prefix DP | Yes | Keeps every boundary it can reach |
| Greedy longest match | No | A long early word can strand the rest |
| Try every split recursively | Yes, but slower | Solves the same suffixes again without memoization |
Walkthrough
Run it on applepenapple with the words apple and pen.
Most boundaries stay false, because no word ends there. Three turn true: apple takes 0 to 5, pen takes 5 to 8, and apple takes 8 to 13.
dp[13] covers the whole string, so the answer is true: apple + pen + apple.
Checkpoint · predict the next step
Step 5 of 15 on the stage: Boundary 4: no word ends here. The pieces after True boundaries are "appl". dp[4] stays False.
dp = [True, False, False, False, False, False, False, False, False, False, False, False, False, False]
Pitfalls
Greedy longest match commits too early. With s = "abca" and the words abc, ab and ca, it takes abc and is stuck with a. The split ab + ca works.
DP never commits. It keeps every boundary it can reach, and later words can start from any of them.
- A false
dp[j]can't start a word, even ifs[j:i]is in the set. - One failed
jdoesn't makedp[i]false. Try the rest.
For s = "abca" and the words ["abc", "ab", "ca"], what should a correct algorithm say?
Complexity
There are n endpoints, and each tries up to n split points. Each check slices s[j:i], which can be n characters long, so this code is O(n³) in the worst case. Trying only the last L split points, where L is the longest word's length, cuts it to O(n · L²).
dp holds n + 1 booleans: O(n) space, plus the word set.
Every endpoint, every split point
- Set up dpOne boolean per boundary.O(n)
- Endpoint and split pairsEvery earlier j for each i.O(n^2)
- Slice and look ups[j:i] can be as long as s.O(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n³) | 1K | 1M | 1B | 1T |
| O(n) | 10 | 100 | 1K | 10K |
Polynomial, where trying every split recursively without memoization is exponential.
In short
Let dp[i] mean the first i characters can be segmented. For each i, check every earlier j where dp[j] is true and s[j..i] is in the dictionary. dp[len] is the answer. A word set gives O(1) membership checks.
Common mistake
Greedy longest-match segmentation, which can commit to a split that dead-ends later.