Difficulty: Medium1-D Dynamic Programming

Word Break

Problem in Plain English

Given a string and a dictionary of words that may be reused any number of times, decide whether the string can be cut into a sequence of dictionary words placed back to back with no gaps.

Problem Statement

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.

The same dictionary word may be reused multiple times, and the words must cover s exactly from the first character to the last with nothing left over.

Note that a greedy first match can be wrong: an early word may fit yet block every completion, while a different first word succeeds.

Constraints

$1 \leq \mathrm{s.length} \leq 300$ .
$1 \leq \mathrm{wordDict.length} \leq 1000$ .
$1 \leq \mathrm{wordDict}[i].\mathrm{length} \leq 20$ .
The string and dictionary words contain only lowercase English letters.
Dictionary strings are unique and may be reused any number of times.

Examples

Example 1

Input: s = "bluecode", wordDict = ["blue", "code"]
Output: true

The word "blue" covers positions 0 through 3 and "code" covers positions 4 through 7. They meet at boundary 4 with no gap or overlap, covering the entire string.

Example 2

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Use "apple", then "pen", then "apple" again. The dictionary may supply the same word repeatedly; the full 13-character string is covered.

Example 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

The prefix "catsand" can be formed as "cats" + "and" or "cat" + "sand", but its leftover "og" is not coverable. The substring "dog" starts after "catsan", which is not a breakable prefix, so finding "dog" alone does not complete the string.

Example 4

Input: s = "a", wordDict = ["a"]
Output: true

The single character is one complete dictionary word. The empty-prefix base case lets the first word end at boundary 1.

Example 5

Input: s = "abcd", wordDict = ["abc", "ab", "cd"]
Output: true

Choosing the first matching word "abc" leaves an impossible "d". Backtrack and choose "ab" + "cd" instead; the first fitting prefix is not always the right one.

Intuition

Place a boundary between words rather than committing to the first matching prefix. In Example 1, the empty prefix ends at boundary 0, "blue" reaches boundary 4, and "code" reaches boundary 8, covering all of "bluecode". A boundary is useful only if the entire prefix before it is already breakable. Different segmentations that reach the same boundary leave the same remaining suffix, so a single boolean per boundary removes repeated work. Dictionary entries describe reusable pieces, not a supply that gets consumed.

Approaches

Recursive Splitting

Solution Details

Reveal Recursive Splitting: intuition, complexity, and code

Intuition

At a start boundary, try each dictionary word that matches exactly there and recursively cover the suffix after it. A success means every chosen piece joined its predecessor without a gap. Failure of one matching word must allow trying the others; the same suffix may be reached by many segmentations and is re-solved each time without memoization.

Step-by-Step Logic

Begin at boundary 0. A recursive call succeeds at boundary n; otherwise it considers every dictionary word in the given order.
Test each word at the current offset without slicing the suffix. In Example 1, "blue" matches at 0, so recurse from 0 + 4 = 4.
At boundary 4, "blue" does not match; continue the loop. "code" matches, so recurse from 4 + 4 = 8.
Boundary 8 equals the length of "bluecode", so return true. Propagate true immediately through boundary 4 and then 0.
If a matching word leads to false, try the next word at the same boundary. If none succeeds, return false. Example 1 stops on its first successful path, so "code" is never tested at boundary 0.

Why It Works

At each call, the prefix before start has been covered by dictionary words. The base case start = n succeeds because no characters remain. Any legal completion has a first dictionary word matching at start, and the loop tries that word; advancing by its positive length leaves exactly the remaining suffix. Conversely, a branch returning true attaches a matching dictionary word to a completely coverable suffix, so it covers the whole string. Induction on the number of remaining characters proves both directions. Words are not removed, allowing reuse, and startsWith checks at an offset avoid allocating a new suffix on each call.

Dry Run

Recursive Splitting: variable states at each step
Event	start	Remaining suffix (display only)	Word tested	Match / recursive result	Action
enter root	0	bluecode	blue	match	recurse at 4
enter child	4	code	blue	no match	continue loop
next word	4	code	code	match	recurse at 8
terminal call	8	empty	none	start equals n	return true
unwind child	4	code	code	child returned true	return true
unwind root	0	bluecode	blue	child returned true	return true; code at start 0 is not tried

Complexity Analysis

Time Complexity

O(DL2^n)

Space Complexity

O(n)

Let n be the string length, D the number of dictionary words, and L their maximum length. Distinct words matching at one offset have distinct lengths, so recursive paths correspond to choices of word boundaries, giving an O(2^n) bound on calls. Each call can scan D words and compare up to L characters per offset match: O(DL 2^n) is a conservative upper bound, not a claim that each matching path uses all dictionary entries. Summing word lengths M gives the tighter upper bound O(M 2^n). Each nonempty word advances at least one character; the stack uses O(n) space, with input string and dictionary shared and no suffix copies. Adversarial length-300 failures are impractical without memoization.

Code

Solution.java

1import java.util.List;2
3class Solution {4    public boolean wordBreak(String s, List<String> wordDict) {5        return dfs(s, wordDict, 0);6    }7
8    private boolean dfs(String s, List<String> wordDict, int start) {9        if (start == s.length()) return true;10        for (String word : wordDict) {11            // Match at an offset without copying; failed choices leave other words available.12            if (s.startsWith(word, start) && dfs(s, wordDict, start + word.length())) {13                return true;14            }15        }16        return false;17    }18}

Hints

Hint 1

A matching word is useful only if the characters before it are already covered. Which boundary would you record?

Hint 2

After a chosen word, only its ending boundary matters for the remaining problem. Reaching the same boundary twice repeats work.

Hint 3

Let dp[i] mean that the first i characters are breakable. Use dp[0] = true and find a true dp[j] followed by a dictionary word s[j:i].

Hint 4

Limit candidate last words to the dictionary maximum length. Include the boundary at i - L and exclude i itself, because words are nonempty.

Edge Cases

A one-character string in the dictionary, such as "a" with ["a"], succeeds using the empty-prefix base case.
A dictionary word longer than s cannot match, but other shorter words may still cover s.
A final leftover such as "og" in "catsandog" invalidates the whole cover even when a long prefix is breakable.
An overlapping-prefix trap, "abcd" with ["abc", "ab", "cd"], requires rejecting the first match and trying the shorter prefix.
Repeated use, "applepenapple" with ["apple", "pen"], is legal; distinct dictionary entries do not imply single-use words.
Many overlapping words followed by a missing final letter, such as a run of a characters ending in b with only a words, repeatedly explores the same suffix in plain recursion.

Common Mistakes and Interview Tips

Returning false as soon as the first matching word fails misses later choices; "abcd" with ["abc", "ab", "cd"] needs the second word.
Marking an end reachable solely because its preceding slice is a word ignores the required dp[j] prefix condition. A "dog" substring does not make "catsandog" breakable.
Leaving dp[0] false prevents the first word from starting; the empty prefix is reachable even though the input string is nonempty.
Removing a matched dictionary entry wrongly forbids reuse, breaking "applepenapple".
Using an inclusive substring end or excluding j = i - L causes off-by-one errors. Code slices cover j through i - 1 and include words of length L.
Reporting O(nL) time for these fresh-slice implementations assumes constant-time slicing and hashing. State the dictionary preprocessing and candidate-character cost, and distinguish peak storage from total allocations.

Key Takeaway

When a sequence must be tiled by allowed pieces, record which prefixes already tile cleanly and extend them piece by piece instead of re-splitting suffixes.