Word Break (LeetCode 139)
Given a string s and a dictionary wordDict of allowed words, decide whether s can be broken up into a run of one or more dictionary words placed back to back with nothing left over.
A dictionary word is free to appear more than once across the breakdown.
Worked Examples
s = "leetcode", wordDict = ["leet","code"]trues = "applepenapple", wordDict = ["apple","pen"]trues = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falsecats + and or cat + sand leaves og, which is not a word, so no split works.⚖️Formal Constraints & Bounds
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.All the strings of
wordDictare unique.
Core Insight
A boolean memo table caches suffix viability, collapsing duplicate recursive subtrees.
Real-World Scenario & Production Applications
Natural language tokenization, URL path segmentation without spaces.
Subproblems & Recurrence Decomposition3 Phases
dp[i] is True if the prefix s[:i] can be fully segmented into dictionary words. dp[0] = True -- the empty prefix needs zero words.
dp = [False] * (len(s) + 1)
dp[0] = TrueStep-by-Step Execution Trace Table
"leetcode" (Root, d=0, remaining="leetcode") | choose "leet"| (startswith("leet") == True) v "code" (d=1, remaining="code", memo check: Miss) | choose "code"| (startswith("code") == True) v "" (d=2, remaining="", Base Case Hit!) ✅ Return True | Memoize memo["code"] = True <-- Bubble Up Memoize memo["leetcode"] = True <-- Bubble Up Step-by-Step Decision Trace
- Step 1 (Root, d=0, remaining="leetcode"): Evaluate dictionary choices:
"code": Does"leetcode"start with"code"? No (Skip)."leet": Does"leetcode"start with"leet"? Yes!
- Step 2 (Choose "leet", d=1, remaining="code"): Chop off
"leet"calldfs("code"). - Step 3 (Suffix "code", d=1):
memocheck: not yet cached. Evaluate dictionary choices:"leet": Does"code"start with"leet"? No (Skip)."code": Does"code"start with"code"? Yes!
- Step 4 (Choose "code", d=2, remaining=""): Chop off
"code"calldfs(""). - Step 5 (Base Case, d=2):
remaining == ""Record Match: Return True ✅. - Step 6 (Memoize & Bubble Up, d=0):
- Cache
memo["code"] = TrueReturnTrue. - Cache
memo["leetcode"] = TrueRecord Final Result: True ✅.
- Cache
s = "leetcode", wordDict = ["leet","code"]Expected:true| 1 | word_set = set(wordDict) |
| 2 | memo = {} |
| 3 | def dfs(start): |
| 4 | if start == len(s): |
| 5 | return True |
| 6 | if start in memo: |
| 7 | return memo[start] |
| 8 | for end in range(start + 1, len(s) + 1): |
| 9 | if s[start:end] in word_set and dfs(end): |
| 10 | memo[start] = True |
| 11 | return True |
| 12 | memo[start] = False |
| 13 | return False |
| 14 | return dfs(0) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Plain backtracking re-derives an answer from scratch every time it visits the same state — and for a string like "aaaaaaa", the same remaining suffix gets explored through wildly different paths, over and over, causing an exponential blowup.
🗺️ The Analogy: A Hiker Who Writes Notes on Dead-End Trail Markers
Imagine a hiker exploring a trail network, trying to reach the exit. Every time they hit a dead end at a specific junction, they pin a note there: "dead end, don't bother trying from here again." The next time any path — even one arriving from a totally different direction — leads back to that same junction, the hiker reads the note and immediately turns around, instead of re-exploring every trail branching off from it all over again.
🔑 The Key Idea in the Code
The key insight is that "can I successfully break the string starting from index start?" only depends on start itself — not on how the recursion arrived there — so the very first time it's computed, the answer can be cached and reused by every future arrival at that same index.
Missing failed-suffix cache: Re-evaluating suffix substrings that were already proven impossible causes TLE. Caching
memo[start] = Falseprevents redundant exponential path exploration.Linear list lookup on
wordDict: Checkings[start:end] in wordDicton a Pythonlisttakes time per prefix. ConvertingwordDictto asetguarantees average lookups.Over-slicing string bounds: Attempting to slice beyond
len(s)or not defining the base casestart == len(s) -> return True.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
String segmentation against a dictionary with overlapping prefix choices.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: memo[start] records whether suffix s[start:] can be segmented into words.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting memoization: repeatedly testing failing suffixes leads to exponential 2^N time.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use top-down DFS with a
memodictionary. From indexstart, I loopendfromstart + 1tolen(s) + 1. Ifs[start:end]is inword_setanddfs(end)returns True, I memoize and return True. If all cuts fail, I memoize False. Each start runs once, tries up to N ends, and each slice costs up to N, so it runs in O(N^3) time andO(N)space."Interview Tip: There are two valid ways to structure the recursion: 1) Index-Based Range Scanning (
for end in range(start + 1, len(s) + 1):with set lookup), or 2) Word-Choice Suffix Matching (for word in wordDict:withremaining.startswith(word)and suffix memoization). Both achieve top-down memoized optimality.
Complexity & Mathematical Proof
O(N^3 + W · L)
Look at the execution steps: Let N = len(s), W = len(wordDict), L = max word length. Building word_set takes O(W · L). memo lets each of the N start indices run its loop once. That loop tries every end from start + 1 to N, and slicing and hashing s[start:end] costs up to N: O(N^2) per start, O(N^3) in all. Capping end at start + L would make it O(N · L^2).
O(N + W · L) Auxiliary
Memoization array of size N + 1, recursion stack of depth N, and word set of size W · L.
T(N) = O(W · L) + ∑_{i=1}^N ∑_{j=i+1}^N O(j - i) = O(N^3 + W · L)
Derivation Progression
O(W · L) hash set
Hashes every dictionary word once.
N suffix start indices
memo[start] records whether s[start:] is segmentable, so each start runs its loop once.
for end ∈ [start+1, N]: s[start:end] ∈ word_set
Up to N slices per start, each O(end - start) to build and hash: O(N^2) per start.
Variable Definitions
Length of the target string s
Number of words in dictionary
Maximum length of any dictionary word
Memory Architecture & Bounds
O(N) Recursion stack depth
O(N + W · L) Memoization cache and word set
O(1) Boolean return
Boundary Best / Worst Cases
when every one-letter prefix is a word, as in s = "aaaa", wordDict = ["a"]: each call cuts after one letter and succeeds.
when no segmentation exists and every start tries every end.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "segment string into dictionary words". Suffix memoization: cache whether can be successfully partitioned.
. Memoization guarantees at most distinct subproblems.
Word Break (LeetCode 139)
Given a string s and a dictionary wordDict of allowed words, decide whether s can be broken up into a run of one or more dictionary words placed back to back with nothing left over.
A dictionary word is free to appear more than once across the breakdown.
Worked Examples
s = "leetcode", wordDict = ["leet","code"]trues = "applepenapple", wordDict = ["apple","pen"]trues = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falsecats + and or cat + sand leaves og, which is not a word, so no split works.⚖️Formal Constraints & Bounds
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.All the strings of
wordDictare unique.
Core Insight
A boolean memo table caches suffix viability, collapsing duplicate recursive subtrees.
Real-World Scenario & Production Applications
Natural language tokenization, URL path segmentation without spaces.
Subproblems & Recurrence Decomposition3 Phases
dp[i] is True if the prefix s[:i] can be fully segmented into dictionary words. dp[0] = True -- the empty prefix needs zero words.
dp = [False] * (len(s) + 1)
dp[0] = TrueStep-by-Step Execution Trace Table
"leetcode" (Root, d=0, remaining="leetcode") | choose "leet"| (startswith("leet") == True) v "code" (d=1, remaining="code", memo check: Miss) | choose "code"| (startswith("code") == True) v "" (d=2, remaining="", Base Case Hit!) ✅ Return True | Memoize memo["code"] = True <-- Bubble Up Memoize memo["leetcode"] = True <-- Bubble Up Step-by-Step Decision Trace
- Step 1 (Root, d=0, remaining="leetcode"): Evaluate dictionary choices:
"code": Does"leetcode"start with"code"? No (Skip)."leet": Does"leetcode"start with"leet"? Yes!
- Step 2 (Choose "leet", d=1, remaining="code"): Chop off
"leet"calldfs("code"). - Step 3 (Suffix "code", d=1):
memocheck: not yet cached. Evaluate dictionary choices:"leet": Does"code"start with"leet"? No (Skip)."code": Does"code"start with"code"? Yes!
- Step 4 (Choose "code", d=2, remaining=""): Chop off
"code"calldfs(""). - Step 5 (Base Case, d=2):
remaining == ""Record Match: Return True ✅. - Step 6 (Memoize & Bubble Up, d=0):
- Cache
memo["code"] = TrueReturnTrue. - Cache
memo["leetcode"] = TrueRecord Final Result: True ✅.
- Cache
s = "leetcode", wordDict = ["leet","code"]Expected:true| 1 | word_set = set(wordDict) |
| 2 | memo = {} |
| 3 | def dfs(start): |
| 4 | if start == len(s): |
| 5 | return True |
| 6 | if start in memo: |
| 7 | return memo[start] |
| 8 | for end in range(start + 1, len(s) + 1): |
| 9 | if s[start:end] in word_set and dfs(end): |
| 10 | memo[start] = True |
| 11 | return True |
| 12 | memo[start] = False |
| 13 | return False |
| 14 | return dfs(0) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Plain backtracking re-derives an answer from scratch every time it visits the same state — and for a string like "aaaaaaa", the same remaining suffix gets explored through wildly different paths, over and over, causing an exponential blowup.
🗺️ The Analogy: A Hiker Who Writes Notes on Dead-End Trail Markers
Imagine a hiker exploring a trail network, trying to reach the exit. Every time they hit a dead end at a specific junction, they pin a note there: "dead end, don't bother trying from here again." The next time any path — even one arriving from a totally different direction — leads back to that same junction, the hiker reads the note and immediately turns around, instead of re-exploring every trail branching off from it all over again.
🔑 The Key Idea in the Code
The key insight is that "can I successfully break the string starting from index start?" only depends on start itself — not on how the recursion arrived there — so the very first time it's computed, the answer can be cached and reused by every future arrival at that same index.
Missing failed-suffix cache: Re-evaluating suffix substrings that were already proven impossible causes TLE. Caching
memo[start] = Falseprevents redundant exponential path exploration.Linear list lookup on
wordDict: Checkings[start:end] in wordDicton a Pythonlisttakes time per prefix. ConvertingwordDictto asetguarantees average lookups.Over-slicing string bounds: Attempting to slice beyond
len(s)or not defining the base casestart == len(s) -> return True.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
String segmentation against a dictionary with overlapping prefix choices.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: memo[start] records whether suffix s[start:] can be segmented into words.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting memoization: repeatedly testing failing suffixes leads to exponential 2^N time.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use top-down DFS with a
memodictionary. From indexstart, I loopendfromstart + 1tolen(s) + 1. Ifs[start:end]is inword_setanddfs(end)returns True, I memoize and return True. If all cuts fail, I memoize False. Each start runs once, tries up to N ends, and each slice costs up to N, so it runs in O(N^3) time andO(N)space."Interview Tip: There are two valid ways to structure the recursion: 1) Index-Based Range Scanning (
for end in range(start + 1, len(s) + 1):with set lookup), or 2) Word-Choice Suffix Matching (for word in wordDict:withremaining.startswith(word)and suffix memoization). Both achieve top-down memoized optimality.
Complexity & Mathematical Proof
O(N^3 + W · L)
Look at the execution steps: Let N = len(s), W = len(wordDict), L = max word length. Building word_set takes O(W · L). memo lets each of the N start indices run its loop once. That loop tries every end from start + 1 to N, and slicing and hashing s[start:end] costs up to N: O(N^2) per start, O(N^3) in all. Capping end at start + L would make it O(N · L^2).
O(N + W · L) Auxiliary
Memoization array of size N + 1, recursion stack of depth N, and word set of size W · L.
T(N) = O(W · L) + ∑_{i=1}^N ∑_{j=i+1}^N O(j - i) = O(N^3 + W · L)
Derivation Progression
O(W · L) hash set
Hashes every dictionary word once.
N suffix start indices
memo[start] records whether s[start:] is segmentable, so each start runs its loop once.
for end ∈ [start+1, N]: s[start:end] ∈ word_set
Up to N slices per start, each O(end - start) to build and hash: O(N^2) per start.
Variable Definitions
Length of the target string s
Number of words in dictionary
Maximum length of any dictionary word
Memory Architecture & Bounds
O(N) Recursion stack depth
O(N + W · L) Memoization cache and word set
O(1) Boolean return
Boundary Best / Worst Cases
when every one-letter prefix is a word, as in s = "aaaa", wordDict = ["a"]: each call cuts after one letter and succeeds.
when no segmentation exists and every start tries every end.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "segment string into dictionary words". Suffix memoization: cache whether can be successfully partitioned.
. Memoization guarantees at most distinct subproblems.