139. Word Break — DSA Atlas

139

MediumOne-Dimensional Dynamic Programming1-D dynamic programming with a hash setPrefix-reachability DP

Word Break

Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused any number of times.

Open official problem prompt ↗

In plain English

Determine whether the whole string can be tiled end-to-end using dictionary words with repetition allowed.

Picture it like this

Laying floor tiles of fixed shapes: you can cover the hallway only if some sequence of available tiles reaches the far wall with no gaps.

Example

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Why: "leetcode" splits into "leet" + "code", both in the dictionary.

Constraints

1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English lettersAll dictionary words are unique

Pattern lesson

See the pattern, then code

Prefix-reachability DP

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. A prefix of length i is breakable if some split point j exists where the prefix of length j is breakable and the substring s[j:i] is a dictionary word.

New words, made simpleKnow these before the algorithm

Segmentation: A cut of s into contiguous substrings that are all dictionary words.
dp[i]: True if the first i characters can be fully segmented.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Exhaustive recursion

Recomputes the same suffixes repeatedly.

Try every prefix word then recurse on the remainder.

Time O(2^n)Space O(n)

Best choiceBottom-up reachability DP

Polynomial and simple; the standard solution.

dp[i] true iff a breakable dp[j] plus dictionary word s[j:i] exists.

Time O(n^2)Space O(n)

The rule we keep true

Invariant

dp[i] is true exactly when s[0:i] is fully segmentable into dictionary words.

Why this is correct

Reasoning

Any valid segmentation of s[0:i] has a last word ending at i and starting at some j; dp[j] certifies the rest, so checking every j finds a valid split if one exists.

The algorithm in three movesSay these aloud before coding

1Put the dictionary into a set for O(1) lookup

dp[0]=True

2Create dp of length n+1 with dp[0]=True (empty prefix)

dp[4]=True via 'leet'

3For each end i, scan start j<i

dp[8]=True via 'code' from dp[4]

4Set dp[i]=True when dp[j] and s[j:i] is a word, then break

5Return dp[n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readempty prefix

2 · AskIs the empty string breakable?

3 · Update statedp[0]=True

4 · ResultYes by definition.

Key takeaway

dp[4] becomes true after matching 'leet', enabling dp[8] via 'code'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Hash the dictionary
Set membership makes each substring check O(length).
2
Lines 6Empty-prefix base case
dp[0]=True so the first real word can anchor.
3
Lines 7-12Fill reachability
For each end, find any breakable split point whose tail word is in the dictionary; break early once found.
4
Lines 13Answer
dp[n] reports whether the full string is segmentable.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A dictionary word longer than s never matches
Repeated words like s='aaaa', dict=['a','aa'] should return true
A single-word exact match
No possible segmentation returns false

Common beginner mistakes

Greedily matching the longest word first can miss valid splits - you must consider all cut points
Forgetting dp[0]=True
Using a list instead of a set, degrading lookups to O(dict)

Check your understanding

Why can't we just greedily match the longest prefix word each time?

Word Break

Word Break

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming