Dynamic Programming · Prefix DP (variable look-back)
LC-139. Word Break
LC-139. Word Break on FaangDeck — Prefix DP (variable look-back) pattern lesson. Brute force to insight, template, Python solution, trap, complexity and…
What's inside this lesson
- Why this problem — a concrete hook, then the problem itself
- Brute force → Insight — what is redundant, and the one idea that removes it
- Spot it — why the pattern fits, and a cheat sheet to recognise it again
- Blueprint → Fill the blanks → Solution — clean, commented Python
- Trace + trap — a step-by-step walkthrough and the near-correct bug, run to show it fail
- Complexity — time and space, with the numbers behind them
- Interview follow-ups — what to say, what they ask next, and where this leads
About FaangDeck: a free, pattern-first DSA curriculum for FAANG interview prep. 217 visual lessons across 19 topics, organised into a 6-phase learning path. Covers Blind 75, NeetCode 150, and Grind 75. 1,286 quiz questions + 1,222 flashcards. No signup, works offline.