Decide whether a string can be split into dictionary words with DP over prefixes in O(n·L), avoiding exponential backtracking. Amazon/Meta classic, run live.
The problem
Return True if s can be split into a sequence of one or more words from words (words may be reused).
Examples
Example 1
Input
word_break('leetcode', ['leet', 'code'])Expected output
True
Example 2
Input
word_break('catsandog', ['cats', 'dog', 'sand', 'and', 'cat'])Expected output
False
+ 3 hidden tests on Submit — reuse words, backtracking would time out.
Edge cases to ask about
- Empty string
- Reused words
- Pathological 'aaaa…b'
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Backtracking every split | O(2ⁿ) | O(n) | Explodes on 'aaaa…ab'. |
| bestDP over prefixes | O(n · L) | O(n) | ok[i] = some word ends at i and ok[i − len] is True. L = distinct word lengths. |
Walkthrough of the optimal approach (try it yourself first)
ok[i] says whether the prefix s[:i] can be segmented; ok[0] = True. For each end position, try every distinct word length L: if ok[end − L] and s[end − L:end] is a word, then ok[end] is True.
Plain backtracking re-explores the same suffixes exponentially often — the hidden "aaa…ab" case is designed to time it out.
Complexity: O(n · L) time, O(n) space. For each of n end positions, try each distinct word length (slicing adds a factor of the word length).
Reveal the reference solution
def word_break(s, words): vocab = set(words) lengths = {len(w) for w in vocab} ok = [True] + [False] * len(s) for end in range(1, len(s) + 1): for L in lengths: if L <= end and ok[end - L] and s[end - L:end] in vocab: ok[end] = True break return ok[-1]
Follow-ups interviewers ask
- Return every possible sentence (Word Break II).
- Use a trie for the dictionary.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Word Break (Dynamic Programming) in Python?
The optimal solution runs in O(n · L) time and O(n) auxiliary space. For each of n end positions, try each distinct word length (slicing adds a factor of the word length).
What is the brute-force approach, and how do you optimise it?
Backtracking every split: O(2ⁿ) time, O(n) space. Explodes on 'aaaa…ab'. DP over prefixes: O(n · L) time, O(n) space. ok[i] = some word ends at i and ok[i − len] is True. L = distinct word lengths.
What follow-up questions do interviewers ask about Word Break (Dynamic Programming)?
Return every possible sentence (Word Break II). Use a trie for the dictionary.