Word Break

Word Break asks whether a string can be chopped into pieces that are all dictionary words. It is the gateway to 1-D dynamic programming — the trick of building one boolean answer per prefix and reusing earlier answers.

The slow way first

The obvious idea: try every way to cut the string. Pick a first word, then recursively try to break the rest. That works, but the same suffix gets re-solved over and over, so it blows up to exponential time on strings with many possible cuts.

The question to ask: what do I keep re-computing? Whether a given prefix of the string is breakable. If I record that answer once, I never have to redo it. That is exactly what a dp array buys us.

The idea

Let dp[i] mean: "can s[:i] be split into dictionary words?" Seed dp[0] = True — the empty prefix is trivially breakable. Then fill the row left to right. For each end i, look for a split point j where dp[j] is already True and the slice s[j:i] is a dictionary word. If both hold, s[:i] is breakable, so set dp[i] = True.

The key insight: a longer prefix is breakable only if some shorter prefix was breakable and the leftover tail is a single word. We build big answers out of small ones we already trust.

Walk through it

Step through the animation. The top row is the string "leetcode"; the row below it is the dp array. We seed dp[0] = True. At i = 4 we try j = 0: dp[0] is True and s[0:4] = "leet" is a word, so dp[4] = True. For i = 5, 6, 7 no split works, so they stay False. At i = 8 we reach j = 4: dp[4] is True and s[4:8] = "code" is a word, so dp[8] = True. The final answer is dp[8].

Pseudocode

put the words into a set            # O(1) "is this slice a word?" lookups
dp = array of False, length len(s)+1
dp[0] = True                        # empty prefix is breakable
for each end i from 1 to len(s):
    for each split point j from 0 to i-1:
        if dp[j] is True and s[j:i] is in the set:
            dp[i] = True
            stop scanning j
return dp[len(s)]

The Python solution

def word_break(s, words):
    words = set(words)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

• words = set(words) turns the list into a set so each s[j:i] in words check is O(1).
• dp has len(s) + 1 slots; dp[i] answers "is s[:i] breakable?"
• dp[0] = True is the seed: the empty prefix is always breakable.
• The outer loop fixes the end i; the inner loop scans every split point j < i.
• Line 7 is the heart: dp[j] must already be True and the tail s[j:i] must be a word.
• When both hold we set dp[i] = True and break — once a prefix is breakable, the reason does not matter.
• We return dp[len(s)]: can the whole string be segmented?

Complexity

We trade O(n) extra space (the dp array) for a huge speed win over the exponential search. The move — cache one answer per prefix and reuse it — is the core of 1-D dynamic programming.

When this pattern shows up

Practice