The problem
Given a string and a list of dictionary words, decide whether the string can be split into a sequence of dictionary words (words may be reused).
Input: s = "leetcode", words = ["leet", "code"] Output: true
Picture it
Picture a strip of letters and a set of word tiles. We mark each position on the strip “reachable” if the letters before it can be completely covered with tiles. Position 0 is reachable. From any reachable position, if a tile matches the next letters, the position after that tile becomes reachable too. The question is whether the end of the strip becomes reachable.
How to recognise it
- You must decide whether a string can be cut into pieces that all come from a given list, with pieces reusable.
- A cut at position i only matters through one question: "can the first i letters be split?" That answer is reused by every later cut.
- The string has at most 300 letters and the dictionary up to 1,000 words of up to 20 letters, so trying every split is hopeless but a table over positions is cheap.
- "Can this prefix be built from allowed pieces" is the 1-D dynamic programming (DP) pattern that also appears in Decode Ways and Coin Change.
Start with brute force
Try each word as the first piece. If the string starts with it, recurse on the rest. Succeed when nothing is left.
def word_break_brute(s, words):
if not s:
return True
for w in words:
if s.startswith(w) and word_break_brute(s[len(w):], words):
return True
return False
Failures are not remembered, so the same suffix is explored many times. For "a" * 28 + "b" with the words a, aa, aaa it already takes several seconds, and the real limit is 300 letters. Time is exponential; space is O(n) for the recursion and slices.
From brute force to the idea
- Find the waste. Different ways of cutting the front often leave the same suffix, and the brute force re-tests it each time.
- Define a table.
ok[i]isTrueif the first i letters can be split into dictionary words.ok[0]isTrue: the empty start needs no words. - Test each position. For position i and each word w, the word would occupy
s[j:i]wherej = i - len(w). Ifj >= 0,ok[j]isTrueands[j:i] == w, thenok[i]isTrue; stop checking words for this i. - Answer.
ok[len(s)].
This is the key idea: a prefix can be split if some word ends at its last letter and the part before that word can be split.
The key idea
ok[i] is True if some word w ends at position i and ok[i − len(w)] is True. This loop tries all W words at each of the n positions, comparing up to L letters each time: O(n · W · L). (The other common version tries every split point j < i and looks s[j:i] up in a set: O(n²) substring checks, each costing up to O(L) once pieces longer than the longest word L are skipped, so O(n² · L) at most.)
Python solution
def word_break(s, words):
ok = [True] + [False] * len(s) # s[:i]?
for i in range(1, len(s) + 1):
for w in words:
j = i - len(w) # w = s[j:i]?
if j >= 0 and ok[j] and s[j:i] == w:
ok[i] = True
break
return ok[len(s)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential: every position can branch into many words, suffixes are re-solved | O(n): recursion depth and slices |
| Table (shown code) | O(n × W × L): n positions, W words, each comparison up to L letters (about 300 × 1,000 × 20 = 6 × 10^6) | O(n): the ok list |
Edge cases
- Empty string: returns
True(ok[0]), although the problem gives at least one letter. - Empty dictionary (
"a",[]): returnsFalse. - Word reuse (
"applepenapple",["apple", "pen"]): returnsTrue. - Almost works (
"catsandog",["cats", "dog", "sand", "and", "cat"]): returnsFalse. - Overlapping words (
"abcd",["a", "abc", "b", "cd"]): returnsTrueviaa,b,cd, althoughabcalso matches at the front and leavesd. - Word longer than the string:
jis negative, so thej >= 0guard skips it. - Dictionary words must be non-empty: an empty word would make
j = iand compare against a position not yet decided. The problem guarantees length at least 1.
Common mistakes
- Starting with
ok[0] = False, so every answer isFalse. - Matching the longest word first and never going back. For
"abcd"above that fails. - Slicing without the
j >= 0check, since a negativejslices from the end. - Comparing the slice before checking
ok[j]. Both tests are needed, but checking the flag first skips most slice comparisons.
Return the number of ways to split the string into dictionary words (words are distinct, order matters). For "aaaa" with ["a", "aa"] the answer is 5. Describe your approach, then write it if you like.
Compare with our answer
Same table, but each cell stores a count, and every matching word adds the count of the position before it.
def count_splits(s, words):
ways = [1] + [0] * len(s)
for i in range(1, len(s) + 1):
for w in words:
j = i - len(w)
if j >= 0 and s[j:i] == w:
ways[i] += ways[j]
return ways[len(s)]
count_splits("aaaa", ["a", "aa"]) is 5, count_splits("aaaaaaa", ["aaaa", "aaa"]) is 2 and count_splits("a", ["b"]) is 0. Time O(n × W × L), space O(n).
A strong answer mentions: ways[0] = 1, adding ways[j] for every match instead of stopping at the first, that the break of the yes/no version has to go, and that distinct words mean no split is counted twice.
1. You must test whether a 300-letter string can be built by joining words from a dictionary, reusing words freely. Which approach fits best?
Whether a prefix splits depends only on shorter prefixes, so a table over positions is O(n × W × L). Longest-first greedy can paint itself into a corner, and counting letters or deleting words once ignores order and reuse.
2. What dominates the running time of the shown code?
There are two nested loops (n positions by W words), and each slice comparison costs up to L. break only helps on success, and the list is built once in O(n).
3. A learner replaces the table with a greedy loop that always removes the longest dictionary word that matches the front. Which input does it get wrong?
For "abcd" the longest match abc leaves d, which cannot be matched, so greedy says False while the table finds a, b, cd and says True. The other three inputs give the right answers (True, True, False) even with greedy.
Score 60% or more and the lesson is marked complete.