Medium
Dynamic Programming
Word Break
A prefix is breakable if some split point is breakable and the remainder is a word.
Approach
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.
Time complexity
O(n² · L)
Space complexity
O(n)
Common mistake
Greedy longest-match segmentation, which can commit to a split that dead-ends later.
See it run, step by step
Generate an interactive lesson for Word Break — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Word Break