Dynamic Programming
Medium
Word Break
Given a string s and a dictionary of strings, return true if s can be segmented into a space-separated sequence of dictionary words.
10 min read
Solve on LeetCodeProblem Understanding
We need to check if the entire string can be built using dictionary words. Words can be reused.
Example: s = "leetcode", dict = ["leet", "code"]
- "leet" + "code" -> Valid
- Output:
true
Algorithm Strategy
We define dp[i] as a boolean: Is prefix s[0...i-1] valid?
Recurrence:dp[i] = true IF exists some j < i such that:
dp[j]is true (prefix ending at j is valid)s[j...i]is in the dictionary.
Base Case: dp[0] = true (empty string).
Interactive Visualization
Step 1 / 1
Initializing...
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.