Word Break
The insight: once you know a shorter prefix of the string can already be broken into valid words, you don't need to re-decide it — you only need to check whether what's left after that break point is itself one whole dictionary word. dp[i] tracks exactly that: "can the first i characters be segmented?", built left to right by checking every earlier breakable prefix j and testing if the remaining chunk s[j:i] is in the dictionary. The base case dp[0] = true (an empty prefix is trivially breakable) is what lets the very first real word get recognized, and the final answer is simply dp[n] — can the whole string be broken this way.
Dynamic Programming
step 1 / 8
Initialize dp[0] = true, base case: empty string can always be segmented
1FUNCTION wordBreak(s, wordDict):2 n = the length of s3 dp = a list of n+1 falses (dp[i] = can first i chars be segmented)4 dp[0] = true (an empty prefix is always breakable)5 FOR i from 1 to n:6 FOR j from 0 to i-1:7 IF dp[j] is true and the substring s[j..i] is in wordDict:8 dp[i] = true9 stop this inner loop10 RETURN dp[n]
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Initialize dp[0] = true, base case: empty string can always be segmented
- i=1: s[0:1]="l" not in wordDict, dp[1] = false
- i=2: s[0:2]="le" not in wordDict, dp[2] = false
- i=3: s[0:3]="lee" not in wordDict, dp[3] = false
- i=4: s[0:4]="leet" in wordDict AND dp[0]=true, dp[4] = true
- i=5: s[0:5]="leetc" not in wordDict, dp[5] = false
- i=8: s[0:8]="leetcode", check j=4: dp[4]=true and s[4:8]="code" in wordDict, dp[8] = true
- Answer: dp[8] = true, s can be segmented as "leet" + "code"
Now solve it yourself
Watching is the first half. The second is writing it without the animation.