Pattern visualizer
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. Animated on: s="leetcode", wordDict=["leet","code"].
Dynamic Programming
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