LeetCode 139 ·
Medium
Word Break
Return true if the string can be segmented into a sequence of dictionary words.
Try it
Step through the core mechanic. The simulator below runs the dynamic programming shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Dynamic programming — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
dp[i] = can the prefix of length i be segmented. dp[i] is true if some j<i has dp[j] true and s[j..i] is a dictionary word. Build left to right.
| Aspect | Value |
|---|---|
| Pattern | Dynamic programming |
| Recognise it by | Can a string be cut into dictionary words? |
| Time complexity | O(n²) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.