139. Word Break

The thing that makes Word Break trickier than it looks is that a locally correct choice can dead-end you globally — grab the longest matching word up front and you can still paint yourself into a corner. That’s the tell for dynamic programming: once you can’t commit greedily, you build every answer from smaller answers you’ve already settled.

The problem

You get a string s and a list of words. Return true if s can be cut into a sequence of those words end to end, where each word may be reused as many times as you like. (Full statement on LeetCode.)

With s = "applepenapple" and words ["apple", "pen"], the answer is true — it splits as apple + pen + apple, reusing apple. But s = "catsandog" with ["cats", "dog", "sand", "and", "cat"] is false: every promising start leaves a tail that no combination of words can cover.

Intuition: is every prefix reachable?

The trap is thinking greedily. Take words ["car", "ca", "rs"] and s = "cars". Grab the longest match first and you take "car", which strands a leftover "s" that no word covers — a dead end. Yet "ca" + "rs" segments it cleanly. Because an early word choice constrains everything after it, you can’t commit to one cut in isolation.

So flip the question from “how do I split s” to “which prefixes of s are reachable?” Define

$dp[i] = \texttt{true if } s[0..i) \text{ can be fully segmented.}$

The empty prefix is reachable for free, so $dp[0]$ is true. Now a prefix ending at i is reachable when there’s some earlier cut point j that is itself reachable and the chunk between them, s[j..i), is a real word:

$dp[i] = \bigvee_{0 \le j < i} \big(dp[j] \;\wedge\; s[j..i) \in \text{words}\big).$

That dp[j] term is what saves you from the greedy trap — it only lets you extend from splits you’ve already proven valid, so every reachable state is built on solid ground rather than a lucky first guess.

Solution

Put the words in a HashSet for $O(1)$ membership, then fill dp left to right. For each end i, scan back for any reachable start j whose gap is a word:

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int n = s.length();

        // dp[i] == true  ->  s[0..i) is segmentable
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;              // empty prefix: vacuously segmentable

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // s[0..j) already works AND s[j..i) is a dictionary word
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;  // reachable; no need to try other j
                    break;
                }
            }
        }
        return dp[n];
    }
}

The break matters for speed but not correctness: once one valid split lands on i, that prefix is settled, so there’s no reason to keep probing other cut points.

Complexity

	Time	Space
Prefix DP (as written)	$O(W + n^3)$	$O(n + W)$

Be honest about the constant the "$O(n^2)$" shorthand hides: the two nested loops give $n^2$ cut-point pairs, but each s.substring(j, i) builds a string of length up to $n$ and then hashes it, so a single pair can cost $O(n)$ — pushing the worst case to $O(n^3)$ for the code as written. Add the one-time $O(W)$ to build the HashSet from the dictionary ($W$ = total characters across all words), and space is the dp array plus that set, $O(n + W)$.

The standard trim is to bound the inner loop by the longest word length $L$ (start j at i - L): no split longer than the longest dictionary word can ever match. That caps substring work and drops the DP part to $O(n \cdot L^2)$ — an asymptotic win, not just a smaller constant, since $L$ replaces $n$ in two of the three factors.

In an interview

Say the greedy failure out loud first — “I can’t just take the longest match, because on cars grabbing car strands an s, when ca + rs would have worked” — then pivot to the prefix DP. That one sentence proves you understand why the problem needs DP, which is worth more than the code. The edge case to name is the base case: $dp[0] = \texttt{true}$ is the seed that makes the whole recurrence fire, and forgetting it leaves every dp[i] stuck at false.

If they push on performance, mention that a Trie over the dictionary lets you walk characters instead of rebuilding and hashing length-$L$ substrings — that’s an asymptotic improvement (roughly $O(n \cdot L^2) \to O(n \cdot L)$), not just a smaller constant. The reuse-a-word-freely flavor here is the same one behind Coin Change (compose a total from a reusable set), and the “cut a string into valid pieces” shape mirrors Decode Ways. Both live under the same DP pattern hub.

References

• LeetCode 139 — Word Break