Problem Statement
Word Break
You are given a string s and a list of allowed words called wordDict. The question is simple to ask: can you chop s into pieces, end to end, so that every piece is a word from the list? You can reuse a word as many times as you want. Return true if it can be done, and false if it cannot.
Signals to notice
Brute force first
Try every possible segmentation recursively — exponential. Many substrings are re-evaluated because different segmentations share common prefixes. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
DP: dp[i] = true if s[0.i-1] can be segmented. For each position i, check all j < i: if dp[j] is true and s[j.i] is in the dictionary, then dp[i] = true. with set lookup. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on s="catsandog", wordDict=["cats","dog","sand","and","cat"]
init: dp=[T,F,F,F,F,F,F,F,F,F] (len 10), dp[0]=True (empty prefix segmentable)
i=3: j=0 dp[0]=T, s[0:3]="cat" in set -> dp[3]=True
i=4: j=0 dp[0]=T, s[0:4]="cats" in set -> dp[4]=True
i=7: j=3 dp[3]=T, s[3:7]="sand" in set -> dp[7]=True (also j=4 "and" works)
i=9: try j=7 "og", j=4 "andog", j=3 "sandog", j=0 "catsandog" — none valid with dp[j]=T -> dp[9] stays False
return dp[9] = False ("catsandog" cannot be fully segmented)What must stay true
dp[i] means the first i characters can be perfectly segmented. If dp[j] is true and the substring from j to i is a valid word, then dp[i] is also true. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
dp[0..n] = false; dp[0] = true
for i in 1..n:
for j in 0..i-1:
if dp[j] and s[j:i] in wordSet:
dp[i] = true; break
return dp[n]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not recognizing the overlapping subproblems — the recursive approach re-solves the same prefixes many times. Memoization or bottom-up DP eliminates this redundancy. The fix is usually to return to the meaning of each move, not just the steps themselves.