Loading…

mediumDynamic ProgrammingLC #139Frequently asked

Word Break

Q: How do you solve Word Break using the Brute Force — Recursion Over Start Index approach?

When to use it: Say this first to establish the split-point recurrence, then flag the exponential re-exploration before optimizing. Reason from the front. To break `s` starting at index `start`, try every prefix `s[start..end)`: if that prefix is a dictionary word, recursively try to break the remaining suffix from `end`. If any choice of `end` lets the rest of the string break cleanly, the whole thing breaks. The base case is `start == n` — we've consumed the entire string, so success. **The mental shift: commit to one word, recurse on the suffix.** Don't try to place all the cuts at once. Just decide where the *first* word ends, then the remainder is the same problem on a shorter string. Because words can repeat, we never remove anything from the dictionary — every word is available again in the suffix. **Why greedy fails and we must try every prefix.** A greedy 'take the longest matching word' can make a locally fine choice that strands the rest. On `"catsandog"` grabbing `"cats"` then `"and"` leaves `"og"`, dead; the only hope is exploring *all* split points, which is exactly what the `any(...)` over `end` does. **Why we don't ship this.** Different prefixes can lead to the same suffix `start`, and the naive recursion re-solves `canBreak(start)` every time it's reached — exponential overlap. Name it, then cache by `start`. Time complexity: O(2ⁿ · L). Space complexity: O(n).

Q: How do you solve Word Break using the Top-Down Memoization approach?

When to use it: The fix once you see the overlap — 'cache canBreak(start) so each suffix is solved once'. Keep the same start-index recursion, but cache `canBreak(start)`. A `memo` array (or map) indexed by start position remembers whether the suffix from that point can be segmented, so each suffix is solved exactly once. **The mental shift: a suffix has one verdict, independent of how you arrived.** In the brute force, the suffix beginning at index `start` might be reached via many different prefix combinations, and each time we re-explore it from scratch. Since the answer for a given `start` is fixed, caching it turns the exponential tree into n unique subproblems. **Why caching `false` matters as much as `true`.** A suffix that *cannot* be broken (like `"og"` in `"catsandog"`) is hit repeatedly through different failing prefixes. Remembering its `false` verdict makes every later visit O(1), which is where most of the speed-up actually comes from on negative cases. **Why the dictionary stays a set.** Membership is the inner-loop hot path. A `HashSet` keeps each `s[start..end)` lookup at O(word length); a `List.contains` would multiply the whole thing by the dictionary size. Time complexity: O(n² · L). Space complexity: O(n).

Q: How do you solve Word Break using the Bottom-Up — dp[] Over Prefix Boundaries (Optimal) approach?

When to use it: The answer they want. Frame it as 'dp[i] = can s[0..i) be segmented; build i from 0 up to n'. Turn the recursion around and build verdicts for prefixes, shortest to longest. `dp[i]` means 'the prefix `s[0..i)` can be fully segmented'. Anchor `dp[0] = true` (the empty prefix needs no words). Then for each end boundary `i`, scan every earlier boundary `j`: if `dp[j]` is true *and* `s[j..i)` is a dictionary word, then `s[0..i)` splits as (a known-good prefix) + (one more word), so `dp[i] = true`. The final answer is `dp[n]`. **The mental shift: index state by the cut position, not the character.** The hard part of segmentation is that cuts can fall anywhere. By making `dp[i]` answer 'is there *any* valid way to end a word exactly at position i?', each `dp[i]` reduces to 'is there an earlier valid cut `j` followed by a single dictionary word `s[j..i)`?'. You're gluing one word onto an already-solved shorter prefix — that's the entire recurrence. **Why dp[0] = true is load-bearing.** Every true entry ultimately chains back to `dp[0]`: the first word of any segmentation needs `dp[0]` to be true so that `s[0..len)` can light up `dp[len]`. Leave `dp[0]` false and nothing ever becomes true — the whole table collapses to false. **Why bottom-up needs no recursion.** Since `dp[i]` only reads `dp[j]` for `j < i`, sweeping `i` upward guarantees every dependency is already final. The dictionary lives in a hash set so each `s[j..i)` test is O(word length), and a small early `break` exits the inner loop the moment `dp[i]` is confirmed true. Time complexity: O(n² · L). Space complexity: O(n).

LCPractice

Dynamic Programming · 10 of 44 · 10 min

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note: the same dictionary word may be reused **multiple times** in the segmentation.

In plain English

Decide whether the whole string can be chopped into consecutive chunks, each of which is a word in the dictionary, reusing words as needed. We don't need the segmentation itself — just whether one exists.

Examples

Example 1

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Note: "leetcode" = "leet" + "code".

Example 2

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Note: "apple" + "pen" + "apple" — note "apple" is reused.

Example 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Note: No segmentation covers the whole string — every path leaves a leftover that isn't a word.

Constraints

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s and wordDict[i] consist of only lowercase English letters
All the strings of wordDict are unique

Clarifying questions5First question: Can dictionary words be reused?Explore questions

Q1.Can dictionary words be reused?
Yes — the same word may appear any number of times in the segmentation. That's why we don't remove used words.
Q2.Must every character be covered?
Yes. The segmentation must consume all of s with no leftover characters — that's what dp[n] (the full length) checks.
Q3.Is the dictionary large enough to matter for lookups?
Up to 1000 words. Put them in a hash set so each membership test is O(word length), not an O(1000) list scan.
Q4.Does the order of words in the dictionary matter?
No. We only test membership of substrings, so the dictionary is just a set.
Q5.Would a greedy longest-match work?
No. On s = 'applepenapple' a greedy that grabs a wrong early chunk can strand the rest. We need DP to consider all split points.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Can s be cut into a sequence of dictionary words? Define dp[i] = 'the prefix s[0..i) is fully segmentable'. dp[0] = true; dp[i] is true if some j < i has dp[j] true AND s[j..i) is a dictionary word. Put the dictionary in a hash set for O(1) lookup. Memoized recursion or a bottom-up dp[] both run in O(n²) (times word-length for substring/lookup).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model the string as partition-by-prefix DP, recognize the overlapping subproblems that make naive recursion exponential, and use a hash set for O(1) dictionary lookups.

Where candidates slip

Greedily matching the longest (or first) word and committing to it, which fails on inputs like 'applepenapple' where an early wrong cut dooms the rest; or doing O(dictSize) list scans instead of a set.

How to stand out

State dp[i] precisely, explain why dp[0] = true anchors it, justify the hash set, and mention the Trie optimization and the Word Break II follow-up that returns actual segmentations.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over Start Index	`O(2ⁿ · L)`	`O(n)`	Say this first to establish the split-point recurrence, then flag the exponential re-exploration before optimizing.	Read
2	Top-Down Memoization	`O(n² · L)`	`O(n)`	The fix once you see the overlap — 'cache canBreak(start) so each suffix is solved once'.	Read
3	Bottom-Up — dp[] Over Prefix Boundaries (Optimal)Optimal	`O(n² · L)`	`O(n)`	The answer they want. Frame it as 'dp[i] = can s[0..i) be segmented; build i from 0 up to n'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCan s split into dictionary words?Greedy longest match?TemptingModel as DPExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over Start Index

TimeO(2ⁿ · L)SpaceO(n)

Say this first to establish the split-point recurrence, then flag the exponential re-exploration before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think about where the FIRST word ends. If s[0..k) is a dictionary word, what's left to solve?

2Hint 2Explore hint

If a prefix s[start..end) is in the dictionary, recurse on the remaining suffix starting at end. Succeed if any prefix leads to a fully consumed string.

3Hint 3Explore hint

Write canBreak(start) = (start == n) OR any end>start with s[start..end) in dict AND canBreak(end).

A · Core idea

Reason from the front. To break s starting at index start, try every prefix s[start..end): if that prefix is a dictionary word, recursively try to break the remaining suffix from end. If any choice of end lets the rest of the string break cleanly, the whole thing breaks. The base case is start == n — we've consumed the entire string, so success.

The mental shift: commit to one word, recurse on the suffix. Don't try to place all the cuts at once. Just decide where the first word ends, then the remainder is the same problem on a shorter string. Because words can repeat, we never remove anything from the dictionary — every word is available again in the suffix.

Why greedy fails and we must try every prefix. A greedy 'take the longest matching word' can make a locally fine choice that strands the rest. On "catsandog" grabbing "cats" then "and" leaves "og", dead; the only hope is exploring all split points, which is exactly what the any(...) over end does.

Why we don't ship this. Different prefixes can lead to the same suffix start, and the naive recursion re-solves canBreak(start) every time it's reached — exponential overlap. Name it, then cache by start.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "leetcode", wordDict = ["leet", "code"]

canBreak(0)

prefix "leet" (0..4) in dict → recurse canBreak(4)

Statetrying suffix from 4

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean wordBreak(String s, List<String> wordDict) { Set<String> words = new HashSet<>(wordDict); return canBreak(s, 0, words); } Explore the full code

solution.javaJava

Brute Force — Recursion Over Start Index — reference

3 teaching notes

1
public boolean wordBreak(String s, List<String> wordDict) {
2
    // Hash the dictionary up front so each membership test is O(word length), not an
3
    // O(dictSize) list scan.
4
    Set<String> words = new HashSet<>(wordDict);
5
    return canBreak(s, 0, words);
6
}
7
 
8
private boolean canBreak(String s, int start, Set<String> words) {
9
    // Base case: consuming the whole string is success — there's nothing left to break.
10
    if (start == s.length()) {
11
        return true;
12
    }
13
    for (int end = start + 1; end <= s.length(); end++) {
14
        // A prefix word AND a breakable suffix — short-circuits to true on the first
15
        // working split.
16
        if (words.contains(s.substring(start, end)) && canBreak(s, end, words)) {
17
            return true;
18
        }
19
    }
20
    return false;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(2ⁿ · L) timeO(n) spaceOpen the invariant and proofExplore the proof

The only thing that determines whether the rest of the string breaks is the starting index of the suffix — the path taken to get there is irrelevant. That 'future depends only on position' property is the hallmark of a problem that memoizes into a clean polynomial DP.

ComplexityO(2ⁿ · L) time, O(n) space — Each start index tries up to n end positions and recurses, and without caching the same suffixes are re-explored across paths → up to 2ⁿ calls. Each substring build / set lookup costs O(L) where L is word length. Stack depth O(n).

E · Edge cases and pitfalls4s = "a", wordDict = ["a"] — canBreak(0): prefix "a" in dict → canBreak(1) hits start==n → true.Explore edge cases

Edge cases handled

s = "a", wordDict = ["a"]canBreak(0): prefix "a" in dict → canBreak(1) hits start==n → true.

Pitfalls

Scanning the wordDict list with contains() on a List instead of a Set — adds an O(dictSize) factor.
Greedy first/longest match — commits to a cut that can strand the rest (false negatives).
Shipping the uncached recursion — exponential, TLEs on adversarial inputs like 'aaaa...a' with dict ['a','aa'].

03.2

Approach 2 of 3

Top-Down Memoization

TimeO(n² · L)SpaceO(n)

The fix once you see the overlap — 'cache canBreak(start) so each suffix is solved once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

canBreak(start) returns the same answer every time it's called. Where can you store it?

2Hint 2Explore hint

Memoize by start index. On entry, return the cached boolean if known; otherwise compute and store it.

3Hint 3Explore hint

memo[start] = any prefix word from start whose suffix also breaks; cache false results too.

A · Core idea

Keep the same start-index recursion, but cache canBreak(start). A memo array (or map) indexed by start position remembers whether the suffix from that point can be segmented, so each suffix is solved exactly once.

The mental shift: a suffix has one verdict, independent of how you arrived. In the brute force, the suffix beginning at index start might be reached via many different prefix combinations, and each time we re-explore it from scratch. Since the answer for a given start is fixed, caching it turns the exponential tree into n unique subproblems.

Why caching `false` matters as much as `true`. A suffix that cannot be broken (like "og" in "catsandog") is hit repeatedly through different failing prefixes. Remembering its false verdict makes every later visit O(1), which is where most of the speed-up actually comes from on negative cases.

Why the dictionary stays a set. Membership is the inner-loop hot path. A HashSet keeps each s[start..end) lookup at O(word length); a List.contains would multiply the whole thing by the dictionary size.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

canBreak(0)

"cat"→canBreak(3); "cats"→canBreak(4)

Stateexplores both

Final resultfalse

C · Code with teaching comments

Reference implementation previewpublic boolean wordBreak(String s, List<String> wordDict) { Set<String> words = new HashSet<>(wordDict); Boolean[] memo = new Boolean[s.length() + 1]; return canBreak(s, 0, words, memo); }Explore the full code

solution.javaJava

Top-Down Memoization — reference

4 teaching notes

1
public boolean wordBreak(String s, List<String> wordDict) {
2
    Set<String> words = new HashSet<>(wordDict);
3
    // Boolean (not boolean) so null means 'uncomputed', distinct from cached
4
    // true/false.
5
    Boolean[] memo = new Boolean[s.length() + 1];
6
    return canBreak(s, 0, words, memo);
7
}
8
 
9
private boolean canBreak(String s, int start, Set<String> words, Boolean[] memo) {
10
    if (start == s.length()) {
11
        return true;
12
    }
13
    // Cache hit — return the stored verdict, including remembered failures, in O(1).
14
    if (memo[start] != null) {
15
        return memo[start];
16
    }
17
    for (int end = start + 1; end <= s.length(); end++) {
18
        if (words.contains(s.substring(start, end)) && canBreak(s, end, words, memo)) {
19
            // Found a working split — record success before short-circuiting out.
20
            memo[start] = true;
21
            return true;
22
        }
23
    }
24
    // No split worked from here; cache the failure so this suffix is never re-explored.
25
    memo[start] = false;
26
    return false;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n² · L) timeO(n) spaceOpen the invariant and proofExplore the proof

Memoization here is the textbook upgrade: a correct recursion whose state is a single integer (start) plus heavy overlap becomes O(states × work-per-state) the moment you add a cache. The intellectual step was realizing the start index fully determines the future — the cache is then mechanical.

ComplexityO(n² · L) time, O(n) space — There are n distinct start indices. Each does an O(n) loop over end positions with an O(L) substring/lookup → O(n² · L) time. The memo plus recursion stack is O(n).

E · Edge cases and pitfalls5s = "aaaaaaa", wordDict = ["a","aa"] — Without memo this explodes; with caching each suffix index is solved once → fast true.Explore edge cases

Edge cases handled

s = "aaaaaaa", wordDict = ["a","aa"]Without memo this explodes; with caching each suffix index is solved once → fast true.
s = "catsandog", ...memo[7]=false for "og" is reused across paths, so the negative answer is reached without re-exploring dead suffixes.

Pitfalls

Using primitive boolean[] (defaults to false) — can't distinguish 'uncomputed' from a cached false; use Boolean[] with null.
Caching only true results — failures are re-explored and you stay slow on negative cases.
List.contains instead of a Set — multiplies runtime by dictionary size.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — dp[] Over Prefix Boundaries (Optimal)

TimeO(n² · L)SpaceO(n)

The answer they want. Frame it as 'dp[i] = can s[0..i) be segmented; build i from 0 up to n'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define dp[i] = 'the first i characters can be segmented'. What's the trivially true base case?

2Hint 2Explore hint

dp[0] = true (empty prefix). For each end i, look back to every split j: if dp[j] is true and s[j..i) is a word, dp[i] is true.

3Hint 3Explore hint

Two nested loops over i (1..n) and j (0..i-1); break out as soon as one valid j is found. Answer is dp[n].

A · Core idea

Turn the recursion around and build verdicts for prefixes, shortest to longest. dp[i] means 'the prefix s[0..i) can be fully segmented'. Anchor dp[0] = true (the empty prefix needs no words). Then for each end boundary i, scan every earlier boundary j: if dp[j] is true and s[j..i) is a dictionary word, then s[0..i) splits as (a known-good prefix) + (one more word), so dp[i] = true. The final answer is dp[n].

The mental shift: index state by the cut position, not the character. The hard part of segmentation is that cuts can fall anywhere. By making dp[i] answer 'is there any valid way to end a word exactly at position i?', each dp[i] reduces to 'is there an earlier valid cut j followed by a single dictionary word s[j..i)?'. You're gluing one word onto an already-solved shorter prefix — that's the entire recurrence.

Why dp[0] = true is load-bearing. Every true entry ultimately chains back to dp[0]: the first word of any segmentation needs dp[0] to be true so that s[0..len) can light up dp[len]. Leave dp[0] false and nothing ever becomes true — the whole table collapses to false.

Why bottom-up needs no recursion. Since dp[i] only reads dp[j] for j < i, sweeping i upward guarantees every dependency is already final. The dictionary lives in a hash set so each s[j..i) test is O(word length), and a small early break exits the inner loop the moment dp[i] is confirmed true.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "leetcode", wordDict = ["leet","code"]

Array state

init

dp[0] = true

i ↓

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Bottom-Up — dp[] Over Prefix Boundaries (Optimal) — optimal

4 teaching notes

1
public boolean wordBreak(String s, List<String> wordDict) {
2
    // Hash set so each s.substring(j, i) membership test is O(word length), not
3
    // O(dictSize).
4
    Set<String> words = new HashSet<>(wordDict);
5
    int n = s.length();
6
    boolean[] dp = new boolean[n + 1];
7
    // The empty prefix is segmentable. Every true entry chains back to this anchor.
8
    dp[0] = true;
9
    for (int i = 1; i <= n; i++) {
10
        for (int j = 0; j < i; j++) {
11
            // A valid earlier cut (dp[j]) plus one dictionary word s[j..i) — the whole
12
            // recurrence in one condition.
13
            if (dp[j] && words.contains(s.substring(j, i))) {
14
                // Prefix s[0..i) is segmentable; break since one witness is enough.
15
                dp[i] = true;
16
                break;
17
            }
18
        }
19
    }
20
    return dp[n];
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n² · L) timeO(n) spaceOpen the invariant and proofExplore the proof

Word Break is the prototypical 'can this sequence be partitioned?' DP, and the dp[i] = OR over (dp[j] AND chunk valid) shape is reusable. Replace the boolean OR with a sum to count segmentations, with a min to minimize pieces, or carry back-pointers to reconstruct the actual words (Word Break II) — same prefix-boundary skeleton, different aggregation.

ComplexityO(n² · L) time, O(n) space — Outer loop over n end positions, inner loop over up to n split points, each doing an O(L) substring/lookup → O(n² · L) time. One dp array of size n + 1 → O(n) space, no recursion stack.

E · Edge cases and pitfalls6s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] — dp[3],dp[4],dp[7] light up but dp[9] never does — no word ends exactly at length 9 from a valid cut → false.Explore edge cases

Edge cases handled

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]dp[3],dp[4],dp[7] light up but dp[9] never does — no word ends exactly at length 9 from a valid cut → false.
s = "aaaa", wordDict = ["a","aa"]Each dp[i] becomes true via multiple j's; dp[4] = true → segmentable.

Pitfalls

Forgetting dp[0] = true — nothing can ever become true and you always return false.
Returning dp[n-1] instead of dp[n] — off-by-one that ignores the last character.
Looping j over the dictionary's word lengths incorrectly, or using List.contains — keep the set and the j-over-prefixes form for clarity.
Rebuilding the set inside the loop — hash it once before the loops.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean wordBreak(String s, List<String> wordDict) { Set<String> words = new HashSet<>(wordDict); int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Greedy longest-match

Committing to the longest matching prefix can leave an unbreakable remainder. On 'catsandog' grabbing 'cats' then 'and' leaves 'og'. Only trying ALL split points (DP) is correct.

Explore the code comparison

Don't write this

i = 0
while i < len(s):
    matched = max((w for w in wordDict if s.startswith(w, i)), key=len, default=None)
    if not matched:
        return False
    i += len(matched)
return True

Write this instead

words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
    for j in range(i):
        if dp[j] and s[j:i] in words:
            dp[i] = True
            break
return dp[len(s)]

List lookup instead of a set

Membership against a List is O(dictSize) per check, so the inner loop becomes O(n · dictSize). Hashing the dictionary once makes each lookup O(word length).

Explore the code comparison

Don't write this

if (dp[j] && wordDict.contains(s.substring(j, i))) {

Write this instead

Set<String> words = new HashSet<>(wordDict);
// ...
if (dp[j] && words.contains(s.substring(j, i))) {

Missing the dp[0] anchor

dp[0] = true represents the empty prefix. Without it, no s[0..len) can ever set dp[len] = true, so every input returns false.

Explore the code comparison

Don't write this

boolean[] dp = new boolean[n + 1];
// dp[0] left false
for (int i = 1; i <= n; i++) { ... }

Write this instead

boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) { ... }

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Prefix-partition DP over a hash-set dictionary

Code pattern to memorize

wordSet = set(wordDict)
dp[0] = True
for i in 1..n:
    dp[i] = any(dp[j] and s[j:i] in wordSet for j in 0..i-1)
return dp[n]

Rules to remember

1State is the prefix boundary: dp[i] = 'can s[0..i) be segmented into dictionary words?'
2dp[0] = true — the empty prefix is trivially segmentable; this anchors every later state.
3dp[i] is true iff there's a split point j with dp[j] true and s[j..i) in the dictionary — a known-good prefix plus one more word.
4Store wordDict in a hash set for O(1) membership; scanning the list each time adds an O(dictSize) factor.
5It's a reachability/boolean OR (any), not a count or a min — you only care whether a segmentation exists.

Use this pattern when

Decide whether a string splits into pieces drawn from a fixed vocabulary
A prefix is valid iff some earlier prefix is valid plus one more allowed chunk
Boolean 'is it reachable?' over positions in a sequence
Substring/segment problems where dictionary membership is O(1) via a set

Choose another pattern when

You must return ALL segmentations → Word Break II, backtracking with memo of lists
You need the minimum number of pieces → switch boolean OR to a min count DP
The dictionary is enormous and words are long → consider a Trie to bound the inner scan
Pieces can overlap or reorder freely → not a left-to-right partition problem

Interview takeaway

Word Break is the canonical 'can this sequence be partitioned?' DP. The unlock is indexing state by a prefix boundary and asking 'is there an earlier valid cut plus one dictionary word?'. Swap the boolean for a count or a list and the same dp drives Word Break II, Palindrome Partitioning, and Concatenated Words.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical prefix-partition Dynamic Programming over a hash-set dictionary. Recognize it whenever a sequence must be split into pieces from a fixed set and a prefix is valid iff an earlier prefix is valid plus one allowed chunk. Same skeleton as Word Break II, Palindrome Partitioning, and Concatenated Words.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Break II
Coming soon
Return ALL segmentations, not just whether one exists. Memoize start → list of sentences and backtrack.
Concatenated Words
Coming soon
Run Word Break on each word using the others as the dictionary — find words built from two or more shorter words.
Palindrome Partitioning
Coming soon
Same prefix-partition DP, but the 'dictionary check' is 'is this substring a palindrome?'.
Perfect Squares
Coming soon
Partition a number instead of a string — minimize pieces (squares) rather than test existence.

Same pattern

←

Longest Increasing Subsequence

Continue · Next problem

Unique Paths

mediumDynamic ProgrammingLC #139Frequently asked

Word Break

LCPractice

Dynamic Programming · 10 of 44 · 10 min

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note: the same dictionary word may be reused **multiple times** in the segmentation.

In plain English

Examples

Example 1

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Note: "leetcode" = "leet" + "code".

Example 2

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Note: "apple" + "pen" + "apple" — note "apple" is reused.

Example 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Note: No segmentation covers the whole string — every path leaves a leftover that isn't a word.

Constraints

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s and wordDict[i] consist of only lowercase English letters
All the strings of wordDict are unique

Clarifying questions5First question: Can dictionary words be reused?Explore questions

Q1.Can dictionary words be reused?
Yes — the same word may appear any number of times in the segmentation. That's why we don't remove used words.
Q2.Must every character be covered?
Yes. The segmentation must consume all of s with no leftover characters — that's what dp[n] (the full length) checks.
Q3.Is the dictionary large enough to matter for lookups?
Up to 1000 words. Put them in a hash set so each membership test is O(word length), not an O(1000) list scan.
Q4.Does the order of words in the dictionary matter?
No. We only test membership of substrings, so the dictionary is just a set.
Q5.Would a greedy longest-match work?
No. On s = 'applepenapple' a greedy that grabs a wrong early chunk can strand the rest. We need DP to consider all split points.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model the string as partition-by-prefix DP, recognize the overlapping subproblems that make naive recursion exponential, and use a hash set for O(1) dictionary lookups.

Where candidates slip

How to stand out

State dp[i] precisely, explain why dp[0] = true anchors it, justify the hash set, and mention the Trie optimization and the Word Break II follow-up that returns actual segmentations.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over Start Index	`O(2ⁿ · L)`	`O(n)`	Say this first to establish the split-point recurrence, then flag the exponential re-exploration before optimizing.	Read
2	Top-Down Memoization	`O(n² · L)`	`O(n)`	The fix once you see the overlap — 'cache canBreak(start) so each suffix is solved once'.	Read
3	Bottom-Up — dp[] Over Prefix Boundaries (Optimal)Optimal	`O(n² · L)`	`O(n)`	The answer they want. Frame it as 'dp[i] = can s[0..i) be segmented; build i from 0 up to n'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over Start Index

TimeO(2ⁿ · L)SpaceO(n)

Say this first to establish the split-point recurrence, then flag the exponential re-exploration before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think about where the FIRST word ends. If s[0..k) is a dictionary word, what's left to solve?

2Hint 2Explore hint

If a prefix s[start..end) is in the dictionary, recurse on the remaining suffix starting at end. Succeed if any prefix leads to a fully consumed string.

3Hint 3Explore hint

Write canBreak(start) = (start == n) OR any end>start with s[start..end) in dict AND canBreak(end).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "leetcode", wordDict = ["leet", "code"]

canBreak(0)

prefix "leet" (0..4) in dict → recurse canBreak(4)

Statetrying suffix from 4

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean wordBreak(String s, List<String> wordDict) { Set<String> words = new HashSet<>(wordDict); return canBreak(s, 0, words); } Explore the full code

solution.javaJava

Brute Force — Recursion Over Start Index — reference

3 teaching notes

1
public boolean wordBreak(String s, List<String> wordDict) {
2
    // Hash the dictionary up front so each membership test is O(word length), not an
3
    // O(dictSize) list scan.
4
    Set<String> words = new HashSet<>(wordDict);
5
    return canBreak(s, 0, words);
6
}
7
 
8
private boolean canBreak(String s, int start, Set<String> words) {
9
    // Base case: consuming the whole string is success — there's nothing left to break.
10
    if (start == s.length()) {
11
        return true;
12
    }
13
    for (int end = start + 1; end <= s.length(); end++) {
14
        // A prefix word AND a breakable suffix — short-circuits to true on the first
15
        // working split.
16
        if (words.contains(s.substring(start, end)) && canBreak(s, end, words)) {
17
            return true;
18
        }
19
    }
20
    return false;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(2ⁿ · L) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls4s = "a", wordDict = ["a"] — canBreak(0): prefix "a" in dict → canBreak(1) hits start==n → true.Explore edge cases

Edge cases handled

s = "a", wordDict = ["a"]canBreak(0): prefix "a" in dict → canBreak(1) hits start==n → true.

Pitfalls

Scanning the wordDict list with contains() on a List instead of a Set — adds an O(dictSize) factor.
Greedy first/longest match — commits to a cut that can strand the rest (false negatives).
Shipping the uncached recursion — exponential, TLEs on adversarial inputs like 'aaaa...a' with dict ['a','aa'].

03.2

Approach 2 of 3

Top-Down Memoization

TimeO(n² · L)SpaceO(n)

The fix once you see the overlap — 'cache canBreak(start) so each suffix is solved once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

canBreak(start) returns the same answer every time it's called. Where can you store it?

2Hint 2Explore hint

Memoize by start index. On entry, return the cached boolean if known; otherwise compute and store it.

3Hint 3Explore hint

memo[start] = any prefix word from start whose suffix also breaks; cache false results too.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

canBreak(0)

"cat"→canBreak(3); "cats"→canBreak(4)

Stateexplores both

Final resultfalse

C · Code with teaching comments

solution.javaJava

Top-Down Memoization — reference

4 teaching notes

1
public boolean wordBreak(String s, List<String> wordDict) {
2
    Set<String> words = new HashSet<>(wordDict);
3
    // Boolean (not boolean) so null means 'uncomputed', distinct from cached
4
    // true/false.
5
    Boolean[] memo = new Boolean[s.length() + 1];
6
    return canBreak(s, 0, words, memo);
7
}
8
 
9
private boolean canBreak(String s, int start, Set<String> words, Boolean[] memo) {
10
    if (start == s.length()) {
11
        return true;
12
    }
13
    // Cache hit — return the stored verdict, including remembered failures, in O(1).
14
    if (memo[start] != null) {
15
        return memo[start];
16
    }
17
    for (int end = start + 1; end <= s.length(); end++) {
18
        if (words.contains(s.substring(start, end)) && canBreak(s, end, words, memo)) {
19
            // Found a working split — record success before short-circuiting out.
20
            memo[start] = true;
21
            return true;
22
        }
23
    }
24
    // No split worked from here; cache the failure so this suffix is never re-explored.
25
    memo[start] = false;
26
    return false;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n² · L) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5s = "aaaaaaa", wordDict = ["a","aa"] — Without memo this explodes; with caching each suffix index is solved once → fast true.Explore edge cases

Edge cases handled

s = "aaaaaaa", wordDict = ["a","aa"]Without memo this explodes; with caching each suffix index is solved once → fast true.
s = "catsandog", ...memo[7]=false for "og" is reused across paths, so the negative answer is reached without re-exploring dead suffixes.

Pitfalls

Using primitive boolean[] (defaults to false) — can't distinguish 'uncomputed' from a cached false; use Boolean[] with null.
Caching only true results — failures are re-explored and you stay slow on negative cases.
List.contains instead of a Set — multiplies runtime by dictionary size.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — dp[] Over Prefix Boundaries (Optimal)

TimeO(n² · L)SpaceO(n)

The answer they want. Frame it as 'dp[i] = can s[0..i) be segmented; build i from 0 up to n'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define dp[i] = 'the first i characters can be segmented'. What's the trivially true base case?

2Hint 2Explore hint

dp[0] = true (empty prefix). For each end i, look back to every split j: if dp[j] is true and s[j..i) is a word, dp[i] is true.

3Hint 3Explore hint

Two nested loops over i (1..n) and j (0..i-1); break out as soon as one valid j is found. Answer is dp[n].

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "leetcode", wordDict = ["leet","code"]

Array state

init

dp[0] = true

i ↓

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Bottom-Up — dp[] Over Prefix Boundaries (Optimal) — optimal

4 teaching notes

1
public boolean wordBreak(String s, List<String> wordDict) {
2
    // Hash set so each s.substring(j, i) membership test is O(word length), not
3
    // O(dictSize).
4
    Set<String> words = new HashSet<>(wordDict);
5
    int n = s.length();
6
    boolean[] dp = new boolean[n + 1];
7
    // The empty prefix is segmentable. Every true entry chains back to this anchor.
8
    dp[0] = true;
9
    for (int i = 1; i <= n; i++) {
10
        for (int j = 0; j < i; j++) {
11
            // A valid earlier cut (dp[j]) plus one dictionary word s[j..i) — the whole
12
            // recurrence in one condition.
13
            if (dp[j] && words.contains(s.substring(j, i))) {
14
                // Prefix s[0..i) is segmentable; break since one witness is enough.
15
                dp[i] = true;
16
                break;
17
            }
18
        }
19
    }
20
    return dp[n];
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n² · L) timeO(n) spaceOpen the invariant and proofExplore the proof

Edge cases handled

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]dp[3],dp[4],dp[7] light up but dp[9] never does — no word ends exactly at length 9 from a valid cut → false.
s = "aaaa", wordDict = ["a","aa"]Each dp[i] becomes true via multiple j's; dp[4] = true → segmentable.

Pitfalls

Forgetting dp[0] = true — nothing can ever become true and you always return false.
Returning dp[n-1] instead of dp[n] — off-by-one that ignores the last character.
Looping j over the dictionary's word lengths incorrectly, or using List.contains — keep the set and the j-over-prefixes form for clarity.
Rebuilding the set inside the loop — hash it once before the loops.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Greedy longest-match

Committing to the longest matching prefix can leave an unbreakable remainder. On 'catsandog' grabbing 'cats' then 'and' leaves 'og'. Only trying ALL split points (DP) is correct.

Explore the code comparison

Don't write this

i = 0
while i < len(s):
    matched = max((w for w in wordDict if s.startswith(w, i)), key=len, default=None)
    if not matched:
        return False
    i += len(matched)
return True

Write this instead

words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
    for j in range(i):
        if dp[j] and s[j:i] in words:
            dp[i] = True
            break
return dp[len(s)]

List lookup instead of a set

Membership against a List is O(dictSize) per check, so the inner loop becomes O(n · dictSize). Hashing the dictionary once makes each lookup O(word length).

Explore the code comparison

Don't write this

if (dp[j] && wordDict.contains(s.substring(j, i))) {

Write this instead

Set<String> words = new HashSet<>(wordDict);
// ...
if (dp[j] && words.contains(s.substring(j, i))) {

Missing the dp[0] anchor

dp[0] = true represents the empty prefix. Without it, no s[0..len) can ever set dp[len] = true, so every input returns false.

Explore the code comparison

Don't write this

boolean[] dp = new boolean[n + 1];
// dp[0] left false
for (int i = 1; i <= n; i++) { ... }

Write this instead

boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) { ... }

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Prefix-partition DP over a hash-set dictionary

Code pattern to memorize

wordSet = set(wordDict)
dp[0] = True
for i in 1..n:
    dp[i] = any(dp[j] and s[j:i] in wordSet for j in 0..i-1)
return dp[n]

Rules to remember

1State is the prefix boundary: dp[i] = 'can s[0..i) be segmented into dictionary words?'
2dp[0] = true — the empty prefix is trivially segmentable; this anchors every later state.
3dp[i] is true iff there's a split point j with dp[j] true and s[j..i) in the dictionary — a known-good prefix plus one more word.
4Store wordDict in a hash set for O(1) membership; scanning the list each time adds an O(dictSize) factor.
5It's a reachability/boolean OR (any), not a count or a min — you only care whether a segmentation exists.

Use this pattern when

Decide whether a string splits into pieces drawn from a fixed vocabulary
A prefix is valid iff some earlier prefix is valid plus one more allowed chunk
Boolean 'is it reachable?' over positions in a sequence
Substring/segment problems where dictionary membership is O(1) via a set

Choose another pattern when

You must return ALL segmentations → Word Break II, backtracking with memo of lists
You need the minimum number of pieces → switch boolean OR to a min count DP
The dictionary is enormous and words are long → consider a Trie to bound the inner scan
Pieces can overlap or reorder freely → not a left-to-right partition problem

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Break II
Coming soon
Return ALL segmentations, not just whether one exists. Memoize start → list of sentences and backtrack.
Concatenated Words
Coming soon
Run Word Break on each word using the others as the dictionary — find words built from two or more shorter words.
Palindrome Partitioning
Coming soon
Same prefix-partition DP, but the 'dictionary check' is 'is this substring a palindrome?'.
Perfect Squares
Coming soon
Partition a number instead of a string — minimize pieces (squares) rather than test existence.

Same pattern

←

Longest Increasing Subsequence

Continue · Next problem

Unique Paths