Word Break

1. Problem & Core Objective

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

s = "leetcode", wordDict = ["leet","code"]      →  true
s = "applepenapple", wordDict = ["apple","pen"] →  true   (apple reused)
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]  →  false

Constraints: 1 <= s.length <= 300 · 1 <= wordDict.length <= 1000 · 1 <= word.length <= 20 · lowercase

What's actually being tested: the boolean DP over prefixes — and specifically that the answer for a prefix is true if any split point works, so the combiner is || rather than + or min. It's also the first question here where the recurrence has an unbounded lookback, which means it can't be rolled.

2. First-Principles Thought Process

The state is a prefix

dp[i] = "can s[0..i) be segmented?" — the prefix of length i.

The last word of a valid segmentation ends at position i and starts at some j. So:

dp[i] = OR over j < i of ( dp[j] AND s[j..i) is in the dictionary )

Read it as: the prefix up to j is segmentable, and the remainder j..i is a single word.

The combiner is ||

Existence questions short-circuit — once a split works, stop looking. That's a real optimisation here, not just a stylistic choice.

dp[0] = true

The empty prefix is trivially segmentable, by the empty sequence of words. Every valid split chain bottoms out there.

Setting it false makes the whole table false, since nothing can ever be the first word.

Why this can't be rolled to O(1)

dp[i] reads dp[j] for every j < i. That's unbounded lookback — no fixed window — so the array is required.

This is the counterexample to the rolling rule established in Climbing Stairs, and it's worth naming as such.

Bounding the inner loop

Words are at most 20 characters, so j only needs to range over i−20 .. i−1. That turns O(n²) into O(n · L) where L is the maximum word length — 300 × 20 = 6,000 instead of 90,000.

A small win here, but the reasoning matters: the inner loop is bounded by the longest word, not by the string.

3. Solution Paths

Approach 1 — Recursion over split points (brute force)

public boolean wordBreak(String s, List<String> wordDict) {
    return canBreak(s, 0, new HashSet<>(wordDict));
}

private boolean canBreak(String s, int start, Set<String> dict) {
    if (start == s.length()) return true;            // consumed everything

    for (int end = start + 1; end <= s.length(); end++)
        if (dict.contains(s.substring(start, end)) && canBreak(s, end, dict))
            return true;                              // short-circuit on success
    return false;
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why exponential?"

Every position can be a split point, so there are 2^(n−1) ways to cut the string, and the same suffix is re-explored from many different prefixes.

The adversarial input is the classic one: s = "aaaa…ab" with wordDict = ["a","aa","aaa",…]. Every prefix is segmentable in many ways, none of them lead anywhere, and the whole space gets explored. At n = 300 that's hopeless.

⭐ "What's being recomputed?"

canBreak(s, end) depends only on end — the suffix from that position. But it's called from every start that can reach it, and recomputed each time.

There are only n distinct values of end, so memoising on it collapses the whole thing to O(n · L).

"Why new HashSet<>(wordDict) rather than using the list?"

List.contains is O(size) — a linear scan of up to 1000 words. HashSet.contains is O(word length) for the hash plus comparison. With the lookup inside a double loop, that's the difference between 10^3 and 20 per check.

Approach 2 — Memoised recursion

public boolean wordBreak(String s, List<String> wordDict) {
    return canBreak(s, 0, new HashSet<>(wordDict), new Boolean[s.length()]);
}

private boolean canBreak(String s, int start, Set<String> dict, Boolean[] memo) {
    if (start == s.length()) return true;
    if (memo[start] != null) return memo[start];

    for (int end = start + 1; end <= s.length(); end++)
        if (dict.contains(s.substring(start, end)) && canBreak(s, end, dict, memo))
            return memo[start] = true;

    return memo[start] = false;
}

• Time O(n² · L) · Space O(n) plus stack

Counter-questions on this approach

⭐ "Why Boolean[] rather than boolean[]?"

Because boolean[] defaults to false, and false is a legitimate answer — "this suffix is not segmentable". There'd be no way to distinguish "computed and false" from "not yet computed", so false results would be recomputed endlessly.

Boolean[] defaults to null, which is outside the answer domain. Same sentinel discipline as -2 in Coin Change, where both -1 and 0 were valid answers.

The alternative is a separate boolean[] computed array, which avoids boxing at the cost of a second array.

"Why does the substring extraction cost O(L)?"

s.substring(start, end) allocates a new string of that length, and hashing it for the set lookup is another O(length). Hence the L factor.

A trie over the dictionary avoids both — you walk characters directly without allocating. That's the optimisation for large inputs.

"What's the recursion depth?"

Up to n = 300 with single-character words. Safe here; the tabulated version has none.

Approach 3 — Tabulation (optimal)

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int maxLen = 0;
    for (String w : wordDict) maxLen = Math.max(maxLen, w.length());

    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;                                    // the empty prefix is segmentable

    for (int i = 1; i <= n; i++)
        for (int j = Math.max(0, i - maxLen); j < i; j++)   // bounded by the longest word
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;                                // short-circuit — one split suffices
            }

    return dp[n];
}

Trace — s = "leetcode", dict = {"leet","code"}, maxLen = 4:

Answer dp[8] = true ✓

• Time O(n · L²) — n positions × L split points × O(L) per substring · Space O(n) plus the dictionary

Counter-questions on this approach

⭐ "Why dp[0] = true?"

The empty prefix is segmentable by the empty sequence of words. It's the base case every split chain bottoms out in — dp[4] is true because dp[0] is true and "leet" is a word.

Setting it false makes the entire table false, since no prefix could ever have a valid first word.

⭐ "Why does the inner loop start at i - maxLen?"

Because the last word can be at most maxLen characters. Any j earlier than i − maxLen would require a word longer than any in the dictionary, so it's provably a wasted check.

That turns the inner loop from O(n) to O(L), giving O(n · L) iterations instead of O(n²) — 6,000 versus 90,000 here.

The Math.max(0, ...) guards the start of the string, where i − maxLen goes negative.

⭐ "Why break after finding one split?"

Because the question is existence. Once any j works, dp[i] is true and further split points can't change that.

That's the || combiner short-circuiting. If the question were count the segmentations, the combiner would be + and the loop would have to run to completion — which is the Word Break II variant.

⭐ "Why can't this be rolled to O(1) space like the earlier questions?"

Because dp[i] reads dp[j] for a range of j, not a fixed pair. Even with the maxLen bound it's a window of up to 20 cells, so you'd need a circular buffer of that size rather than two scalars.

It's the counterexample to the rolling rule: bounded lookback rolls, unbounded doesn't — and here it's bounded only by the dictionary's longest word, not by a constant in the recurrence.

"Why is substring inside the loop acceptable?"

It's O(L) per call and allocates. With n · L iterations that's O(n · L²) = 300 × 400 = 120,000 character operations — fine here.

A trie removes it entirely: walk characters from position j forward, checking membership as you go, with no allocation. That's the right answer if the dictionary were large or L bigger.

"What if a dictionary word doesn't appear in s at all?"

Harmless — it's simply never matched. The maxLen computed from it could make the inner loop wider than necessary, which is a minor inefficiency rather than a correctness issue.

Comparison

4. Why the Optimal Wins

The recursion re-explores the same suffixes from many prefixes; there are only n distinct suffixes, so memoising collapses it.

Tabulation removes the recursion, and bounding the inner loop by the dictionary's longest word cuts O(n²) split-point checks to O(n · L).

The framing worth keeping:

dp[i] = "is the prefix of length i segmentable?" — true if ANY split point j has dp[j] true and s[j..i) in the dictionary. Existence means ||, so break on the first success. And the inner loop is bounded by the longest word, not by the string.

Plus the sentinel lesson: with a boolean answer, boolean[] has no room for "not computed" — use Boolean[] or a separate flag array.

5. Java Prerequisites

Boolean DP with the existence combiner

dp[0] = true;
for (int i = 1; i <= n; i++)
    for (int j = Math.max(0, i - maxLen); j < i; j++)
        if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }

Boolean[] for memoisation — boolean[] can't distinguish "false" from "not computed", because false is a real answer.

HashSet over List — List.contains is O(size); with 1000 words inside a double loop that dominates.

maxLen bound — the last word can't exceed the longest dictionary word.

substring is O(L) and allocates — a trie avoids both.

6. Interview Communication Guide

Clarifying questions: Can dictionary words be reused (yes)? Must the whole string be consumed (yes)? Can the dictionary contain duplicates (harmless — the set deduplicates)? Is an empty string segmentable (the constraint says s.length >= 1, but dp[0] = true is the base case)?

The pitch

"The state is a prefix: dp[i] is 'can the first i characters be segmented?'.

A valid segmentation's last word ends at i and starts at some j. So dp[i] is true if there's any j where dp[j] is true and s[j..i) is a dictionary word.

The combiner is || — this is an existence question, not a count or an optimum. So I break on the first split that works; further ones can't change the answer. If the question were count the segmentations, the combiner would be + and the loop would have to run to completion.

dp[0] = true is the base case: the empty prefix is segmentable by the empty sequence. Setting it false makes the whole table false, since nothing could be the first word.

One real optimisation: the inner loop only needs to consider j from i − maxLen to i − 1, where maxLen is the longest dictionary word. Anything earlier would require a word longer than any that exists. That's O(n · L) iterations instead of O(n²) — 6,000 versus 90,000 here.

The naive recursion is O(2^n); the adversarial input is 'aaa…ab' with words ['a','aa','aaa',…], where every prefix splits many ways and none lead anywhere.

Two details worth flagging. If I memoise rather than tabulate, the memo must be Boolean[] not boolean[] — false is a legitimate answer, so a primitive array can't distinguish it from 'not yet computed'.

And this one can't be rolled to O(1) space, unlike the earlier questions in this section. dp[i] reads a range of previous cells rather than a fixed pair, so the array is required."

Edge cases to volunteer:

Name "catsandog". Both "cats" and "cat" are valid prefixes, so a greedy left-to-right match commits to one and fails. The DP tries all split points, which is exactly why greedy doesn't work here.

7. Follow-Up Questions — Modified Constraints

⭐ "Return all possible segmentations, not just whether one exists."

Word Break II (LC 140). Now it's backtracking guided by the DP — first compute dp[] to know which prefixes are viable, then only explore those branches. Without the DP pre-pass, the adversarial input explodes; with it, dead branches are pruned immediately.

Output can still be exponential, so the complexity is O(n · L + output).

⭐ "Count the segmentations instead."

Change boolean[] to int[] and || to +: dp[i] += dp[j] for every valid split. The break must go, since all splits now contribute. Counting and existence differ by exactly the combiner and the short-circuit.

"What if the dictionary had 10^5 words of length up to 100?"

HashSet lookups with O(L) hashing get expensive, and maxLen = 100 widens the inner loop. A trie is the right structure: walk forward from j one character at a time, checking isEnd as you go, with no substring allocation and early abandonment when no word has that prefix.

"What if s were 10^5 characters?"

O(n · L²) with L = 20 is 4 × 10^7 — still viable. The trie version is O(n · L) and would be the safer choice.

"What if words could be used at most once?"

Much harder — the state must track which words are consumed, so it becomes dp[i][usedSet], exponential in the dictionary size. Reusability is what keeps this polynomial.

"Find the segmentation with the fewest words."

Change boolean to int and || to min, with dp[i] = min(dp[j] + 1). Same structure, different combiner — the third variant of the same recurrence.