1. Dictionary set
Set lookup makes word checks fast.
const words = new Set(wordDict)Typorithm · medium
Word Break
▷ Interactive algorithm labword-break-dpdynamic-programmingstringsetsegmentation
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Word Break
Dynamic Programming
Word Break checks whether each prefix can be segmented into dictionary words.
The state says whether a prefix is segmentable.
For each end, try every earlier split point.
A hash set gives fast dictionary lookup.
Preparing algorithm lab…
01
State: dp[end] means prefix s[0:end] works.
02
Base: empty prefix is true.
03
Transition: dp[start] and word suffix.
04
Time O(n^2) substring checks.
function wordBreak(s, wordDict) {
const words = new Set(wordDict);
const dp = Array(s.length + 1).fill(false);
dp[0] = true;
for (let end = 1; end <= s.length; end++) {
for (let start = 0; start < end; start++) {
if (dp[start] && words.has(s.slice(start, end))) {
dp[end] = true;
break;
}
}
}
return dp[s.length];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Empty prefix
The empty prefix can always be segmented.
dp[0] = true3. Valid split
A prefix is valid if an earlier prefix is valid and the suffix is a word.
if (dp[start] && words.has(s.slice(start, end)))4. Stop early
Once dp[end] is true, no more starts are needed.
breakA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.