Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Word Miner.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Word break matches the clues
- 2Keep this true after every move: reachable[end] is true exactly when the prefix ending there can be fully segmented
- 3Reach the result within O(n squared) substring checks
Rules and pressure
- Target cost: O(n squared) substring checks
- State rule: reachable[end] is true exactly when the prefix ending there can be fully segmented
Lesson 1 of 3
Live algorithm trace
Word break
Complete execution1 of 5
Seed the empty prefix as a valid starting boundary.
1
reachable[0] = true2
for each prefix end3
try every earlier cut4
if reachable[cut] and suffix is a word5
mark this prefix reachable and stop6
return reachable[text length]dictionary = leet,codereachable0 = true
Truth to preserve / Cost target
Truth to preserve
reachable[end] is true exactly when the prefix ending there can be fully segmented
Cost target
O(n squared) substring checks
A prefix is segmentable when some earlier segmentable prefix is followed by a dictionary word. The same word may be reused at any later cut.
Your call · What should guide every step of this algorithm?