Word Break
Word Break: can s be segmented into a sequence of dictionary words? (The backtracking variant prints every segmentation.)
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of only lowercase English letters.
- All the strings of wordDict are unique.
Intuition
Word break asks whether a string can be cut into a sequence of dictionary words. The obvious recursion tries every dictionary word as a prefix and recurses on what is left — correct, but exponential, and it is worth seeing exactly where the waste is.
Consider "aaaaaaa" with the dictionary ["a", "aa"]. There are many different ways to reach position 4, and the naive recursion re-solves the suffix starting at position 4 once for each of them. The work is duplicated because it does not depend on the path taken:
- Whether the suffix from index i is breakable depends only on i — never on how the prefix before it was cut.
That is the definition of an overlapping subproblem, and it makes this a textbook memoisation target. Compute the answer for each starting index once and reuse it, and the exponential tree collapses to n distinct subproblems.
Written as a table, dp[i] is true when the suffix beginning at index i can be segmented. The empty suffix at the end is trivially breakable, so dp[n] = true. Working from right to left, dp[i] is true if some dictionary word matches at position i and the rest after that word is itself breakable. The answer for the whole string is dp[0].
String-partition DP: dp[i] asks whether the suffix starting at i can be segmented. Every cut point is a subproblem, and the answer chains right-to-left. Reach for this whenever a string must be split into pieces drawn from a set — palindrome partitioning and word-break II share the skeleton.
Approach
Before reading on: price up what the brute force costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n² · L) time and O(n) space.
See why the naive recursion repeats work
Trying every prefix word and recursing on the remainder re-solves the same suffix once per path that reaches it. The result depends only on the starting index, so recomputing it is pure waste — that observation is what turns this into a DP problem.
Define the table over positions
Let dp[i] mean the suffix starting at index i is breakable into dictionary words. There are n + 1 entries, one per position including the end. Indexing by position rather than by substring is what keeps the table one-dimensional.
Anchor the base case at the end
Set dp[n] = true: the empty suffix requires no words and is breakable by definition. Every other entry is ultimately justified by chaining back to this one, so getting it right matters more than it looks.
Fill the table right to left
For each i from n − 1 down to 0, set dp[i] true if some dictionary word w matches the string at i and dp[i + len(w)] is already true. Both halves are required — a word matching is useless if what follows it cannot be broken.
Read the answer from dp[0]
dp[0] asks whether the entire string is breakable, which is the question posed. No traversal of the table is needed at the end; the single cell holds the result.
Use a set for the dictionary
Membership tests dominate the inner loop, so store the words in a hash set for O(1) lookup rather than scanning a list. Bounding the inner loop by the longest word length avoids checking substrings that could never match.
Cost of the tabulation
There are n positions, each trying up to m words with a substring comparison of up to length k, giving O(n · m · k) time and O(n) space for the table. Compare that with the exponential naive version — the entire gain comes from computing each dp[i] exactly once.
Solution & live demo
Common pitfalls
Greedily taking the longest matching prefix
while s:
for w in sorted(words, key=len, reverse=True):
if s.startswith(w):
s = s[len(w):]
breakfor i in range(n - 1, -1, -1):
for j in range(i + 1, n + 1):
if s[i:j] in words and dp[j]:
dp[i] = True; breakOn s = "aaaaab" with words ["aaaa", "aaa", "b"], taking the longest first strands the rest. A wrong early cut can only be discovered later, so every cut point has to stay on the table.
Leaving dp[n] false
dp = [False] * (n + 1)
dp = [False] * (n + 1) dp[n] = True
dp[n] represents the empty suffix, which is trivially segmentable — it's the base case every chain terminates in. Without it no dp[i] can ever become true and the answer is always false.
Keeping wordDict as a list
if s[i:j] in wordDict:
words = set(wordDict) if s[i:j] in words:
Membership in a list is a linear scan, so the inner test becomes O(m) and the whole solution O(n²·m). A set makes it O(1) — a one-line change that dominates the runtime.
Edge cases
Dictionary words are reusable — dp naturally allows it.
dp explores every word start, not just greedy longest.