Word Break

Learning goal: Recognize Word Break as a question about whether the full string has at least one valid sequence of dictionary-word pieces.

Core idea A valid segmentation must cover every character exactly once, from the beginning to the end. We do not need to construct every segmentation; we only need a boolean answer. The important observation is that a successful segmentation of a prefix gives us a trustworthy starting point for extending the solution.

Algorithm plan

• Start at the left edge of the string.
• Consider possible endpoints for the next word.
• Remember which prefixes are already breakable.
• Return whether the prefix ending at len(s) is breakable.

Micro-example For applepenapple, the prefixes ending after apple and applepen are breakable. The final apple extends the breakable prefix to the entire string.

Pitfalls

• A valid-looking first word does not guarantee that the suffix can be completed.
• The answer concerns the entire string, not merely a breakable prefix.
• Dictionary words can be reused, so a word is not consumed after one use.

Recap

• The target is complete coverage of s.
• Prefix answers can be reused.
• The final prefix determines the result.

Learning goal: Define the DP state so every valid segmentation is represented by a split point.

Core idea Let dp[i] mean that the first i characters, s[0:i], can be segmented into dictionary words. To decide dp[i], try an earlier boundary j. If dp[j] is true and the remainder s[j:i] belongs to the word set, then the prefix ending at i is breakable.

Recurrence

dp[i] = true if there exists j with 0 <= j < i such that dp[j] is true and s[j:i] is in wordSet.

The empty prefix is the base case: dp[0] = true. A set makes the dictionary lookup constant time on average, while the substring length contributes the factor L.

Micro-example For i = 8 in applepenapple, choose j = 5. Since dp[5] is true and s[5:8] is pen, dp[8] becomes true.

Pitfalls

• Only split points with dp[j] = true can extend a solution.
• Use half-open slices such as s[j:i]; i is excluded.
• Do not confuse the word set with a set of prefixes.

Recap

• State: breakability of a prefix.
• Transition: breakable prefix plus dictionary remainder.
• Base case: dp[0] = true.

Learning goal: Turn the recurrence into a bottom-up algorithm with predictable bounds.

Core idea Process prefix lengths from left to right. When computing dp[i], inspect every earlier boundary j from 0 through i - 1; a true state lets us test the candidate word s[j:i]. We can stop early for that i once one valid split is found, because the state is boolean.

Algorithm plan

1. Put every dictionary word into wordSet.
2. Allocate dp with n + 1 entries, all initially false.
3. Set dp[0] = true for the empty prefix.
4. For each i from 1 to n, test earlier j values.
5. Set dp[i] when dp[j] is true and s[j:i] is in wordSet.
6. Return dp[n].

word_set = set(wordDict)
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 word_set:
            dp[i] = True
            break
return dp[len(s)]

Micro-example At i = 13, j = 8 gives dp[8] = true and s[8:13] = "apple", so the answer becomes true.

Pitfalls

• Set dp[0] before processing any nonempty prefix.
• Do not skip j = 0; the first word may begin at the string start.
• Preserve the original indices when slicing.

Recap

• Fill left to right.
• Try all earlier boundaries.
• A word set supplies efficient membership tests.

Learning goal: Trace how reachable prefix boundaries grow until they cover the entire example.

Core idea The walkthrough uses s = "applepenapple" and wordDict = ["apple", "pen"]. Begin with dp[0] = true. Most prefix lengths remain false because their suffixes are not complete dictionary words; the meaningful discoveries happen at indices 5, 8, and 13.

Recurrence

For each endpoint i, inspect j < i:

dp[i] = OR over j of (dp[j] AND s[j:i] in wordSet)

The true states form a chain: 0 -> 5 -> 8 -> 13. Each arrow corresponds to one dictionary word, and the final node is the answer.

Micro-example

• i = 5, j = 0: s[0:5] is apple, so dp[5] = true.
• i = 8, j = 5: s[5:8] is pen, so dp[8] = true.
• i = 13, j = 8: s[8:13] is apple, so dp[13] = true.

Pitfalls

• A false dp[j] cannot support a later word, even if s[j:i] is in the set.
• The letters in the string do not need to be unique; only boundaries matter.

Recap

• Reachable indices are 0, 5, 8, and 13.
• Their words are apple, pen, and apple.
• dp[13] = true is the final result.

Learning goal: Understand why local word choices are unsafe and how the DP avoids dead ends.

Core idea A greedy longest-match strategy chooses the longest dictionary word that fits at the current position. That decision may consume characters needed by a later word, even when a shorter choice would lead to a complete solution. DP does not commit: it records every reachable boundary and lets future states choose among them.

Algorithm plan

• Treat each dp[i] as an independent yes/no question.
• Preserve all true split points rather than selecting one word permanently.
• Check the empty prefix and the final prefix explicitly.
• Test cases with repeated words, overlapping words, and impossible suffixes.

Micro-example With s = "ab" and words ['a', 'ab'], choosing ab works here. But with s = "abca" and words ['abc', 'ab', 'ca'], a longest-first choice can miss the valid split ab + ca.

Pitfalls

• Do not return false after one candidate fails; try another j.
• Do not return true merely because a dictionary word matches a prefix.
• Empty strings are represented by dp[0], not by a special dictionary word.

Recap

• Greedy decisions discard useful boundaries.
• DP keeps all reachable boundaries.
• Edge-case testing should include dead-end suffixes and overlapping words.

Learning goal: Justify the target complexity and recognize the reusable DP pattern.

Core idea There are n endpoint positions, and each endpoint may inspect up to n earlier split points. Creating or checking the slice s[j:i] can involve up to L characters, where L is the maximum dictionary-word length, so the total time is O(n² · L). The boolean array and word set use linear space in the relevant input sizes; the DP portion itself is O(n).

Recurrence

dp[i] = exists j < i: dp[j] AND s[j:i] in wordSet

This is a general pattern: define a state for a prefix, then extend every reachable state with a valid next segment. The answer is the state for the full input.

Micro-example For applepenapple, the DP stores 14 prefix states and discovers the chain 0 -> 5 -> 8 -> 13. It never needs to enumerate all possible segmentations.

Pitfalls

• If substring creation is treated as O(1) in an implementation, the stated L factor may be hidden rather than removed.
• Do not claim O(n) time merely because the DP array has O(n) entries.
• If counting dictionary storage, include the total number of characters in the words.

Recap

• Time: O(n² · L).
• DP space: O(n); dictionary storage is additional.
• Prefix reachability avoids greedy dead ends and repeated recursion.