Word Break
Can a string be cut into dictionary words? A boolean DP where each position asks about every earlier one
Problem Statement
Given a string s and a dictionary of words, return true if s can be split into a sequence of one or more dictionary words. Words may be reused.
Input: s = "leetcode", words = ["leet", "code"]
Output: true "leet" + "code"
Input: s = "applepenapple", words = ["apple", "pen"]
Output: true "apple" + "pen" + "apple" — reuse is allowed
Input: s = "catsandog", words = ["cats", "dog", "sand", "and", "cat"]
Output: falseIntuition
The greedy attempt fails, and the third example is built to show it.
"catsandog" with ["cats", "dog", "sand", "and", "cat"]
Greedy, longest match first:
"cats" ✓ → left with "andog"
"and" ✓ → left with "og"
"og" ✗ → stuck. Report false?
But try the other branch:
"cat" ✓ → left with "sandog"
"sand" ✓ → left with "og"
"og" ✗ → also stuckHere both branches fail so false is right — but greedy had no way to know that without checking both. Change the input slightly and the shorter first match is the one that works. You must try every split point.
Recursion does that, and immediately repeats itself: "applepenapple" reaches the suffix "apple" down several different paths, and re-solves it each time.
The insight
Ask one question per position: can the first i characters be broken up completely?
ok[i] = true if there is some j < i where
ok[j] is true AND s[j..i] is a word
└ prefix works └ the rest is one wordok[0] = true — an empty string is trivially breakable. Work left to right, and each position only consults answers already settled.
The shape is worth naming: this is reachability. Position 0 is reachable, and a word lets you jump from one reachable position to another. The question is whether the end is reachable — the same structure as Jump Game, with words instead of jump lengths.
Approach
Put the dictionary in a set
Membership tests happen inside a double loop, so O(1) lookup matters. A list would make the whole solution O(n² · k).
Create ok of length n + 1, with ok[0] = true
Index i means "the first i characters". The extra slot is the empty prefix.
For each end position i, try every start position j
If ok[j] is true and s[j:i] is in the dictionary, then ok[i] is true. Stop at the first success — one valid split is enough.
Solution
def word_break(s: str, word_dict: list[str]) -> bool:
"""Can s be split entirely into dictionary words?
ok[i] is True when the first i characters can be broken up.
"""
words = set(word_dict)
n = len(s)
ok = [False] * (n + 1)
ok[0] = True # empty prefix
for i in range(1, n + 1):
for j in range(i):
if ok[j] and s[j:i] in words:
ok[i] = True
break # one valid split is enough
return ok[n]The break matters. Without it the inner loop keeps scanning after the answer is settled — correct but wasteful, and it obscures that only existence is being asked.
A useful pruning
The inner loop only needs to look back as far as the longest word in the dictionary. A split at j where i - j exceeds that length can never match anything.
max_len = max(len(w) for w in words)
for j in range(max(0, i - max_len), i):With short words and a long string this turns O(n²) into roughly O(n · max_len) — a real saving, and it costs one line.
Complexity Analysis
Time Complexity
O(n² · k)
Space Complexity
O(n)
Time — n² position pairs, and each slices a substring of length up to k and hashes it. The slicing is easy to overlook; it is why the max_len pruning helps.
Space — the boolean array plus the set of words.
Edge Cases
Related Problems
- Jump Game — the same reachability shape, where greedy is safe
- Coin Change — try every option at each step, minimising instead of testing
- Climbing Stairs — the simplest version of "reach position n"