Lesson 55 — DP IX: Segmentable Prefixes

~25 minutes · Day 72 · dynamic programming

Tonight's interview shape is Word Break: given a string and a dictionary of words, decide whether the string can be split into valid dictionary chunks. The hard part is not checking one split. The hard part is avoiding the same suffix question over and over.

The invariant

dp[i] answers “can the first i characters be segmented?” — true iff some earlier true dp[j] is followed by a dictionary word spanning j to i.

That sentence is the whole pattern. A true cell means a prefix is usable ground. From that ground, one dictionary word can carry you to a later true cell.

Word Break: the slow way first

The brute force is to try every possible sequence of cuts: first word here, next word there, then recurse on the remaining suffix. That is exponential, O(2^n), because the same starting positions get retried through many different cut paths.

Dynamic programming keeps only the useful yes/no answer for each prefix. Use the four DP questions from the training plan:

• State: dp[i] means the first i characters can be segmented.
• Transition: if dp[j] is true and a dictionary word spans j to i, then dp[i] is true.
• Base: dp[0] = True, because the empty prefix is already segmented.
• Answer: return dp[len(s)].

Python's set removes duplicate dictionary words, and str.startswith can test whether a word starts at a chosen index.

def wordBreak(s, wordDict):
    words = set(wordDict)                 # unique dictionary words
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                          # empty prefix works
    for j in range(n + 1):
        if not dp[j]:
            continue                      # cannot extend a false prefix
        for word in words:
            i = j + len(word)
            if i <= n and s.startswith(word, j):
                dp[i] = True              # word spans j -> i
    return dp[n]

The state space

Transfer: same question, new costume

A product code is valid if it can be assembled from approved chunks. Given s = "applepenapple" and chunks ["apple", "pen"], predict the state, transition, base case, and answer location before opening the reveal.

What the trade buys you

Here n is the string length, W is the number of dictionary words, and L is the longest word length. The memory buys you a promise: each prefix question is stored once.

Practice — answer before you scroll past

dp = [False] * (len(s) + 1)
for j in range(len(s) + 1):
    if dp[j]:
        # try words from j

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Word Break — predict the prefix state, attempt the DP table, compare only after your attempt, then encode the invariant in your own words.

For the encode step, write four short sentences: state, transition, base case, answer location. That is the DP self-check gate for this lesson.