Word Break: Segmentation as Reachability DP

If you interview at Amazon, Meta, Google, expect some version of "Word Break". It is rated Medium, and it falls squarely into the Dynamic Programming pattern — pattern-first preparation beats grinding random problems every time. Part 9 of 11 in the Dynamic Programming arc.

The Problem

Given a string and a dictionary, return whether the string can be segmented into a sequence of dictionary words (reusable). Search-flavored on the surface — the naive recursion branches exponentially — but the state space is just n prefixes, which is the entire point.

Input:  s = "leetcode", dict = ["leet", "code"]
Output: True
"applepenapple" with ["apple", "pen"] is also True — words reuse.

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Segmentation validity of the whole depends only on validity of prefixes: dp[i] — can the first i characters be segmented — is true when some earlier true prefix j extends by a dictionary word s[j:i]. Exponential-looking recursion over a linear state space is the most common DP disguise at Meta and Amazon.

The Approach

dp[0] = True (empty prefix). For each end position i, scan candidate split points j — or, tighter, scan only lengths up to the longest dictionary word, which turns O(n²) substring checks into O(n · L). Convert the word list to a set first; substring hashing dominates the cost.

The BFS framing (positions as nodes, dictionary words as edges) is equivalent and sometimes clearer — reachability of position n. Offering both framings signals the pattern is understood, not memorized.

Python Solution

def word_break(s: str, word_dict: list[str]) -> bool:
    """True if s segments into dictionary words (reusable)."""
    words = set(word_dict)
    max_len = max(map(len, words), default=0)
    n = len(s)
    dp = [True] + [False] * n          # dp[i]: s[:i] segmentable
    for i in range(1, n + 1):
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

Complexity

• Time: O(n·L·W) — n end positions, L max word length, W substring hash cost
• Space: O(n) — the reachability array plus the word set

Interview Tips and Follow-Ups

• The max-word-length bound on the inner loop is the optimization interviewers wait for — without it, long strings with short dictionaries do pointless work.
• Word Break II (return all segmentations) is exponential in output — memoized backtracking, and say the output-size caveat before coding it.
• The famous adversarial case ('aaaa...b' with all-a dictionaries) is why memoization is mandatory — quote it when explaining the naive blowup.

More Dynamic Programming problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.