Coding · Dynamic programming
Word Break II
- Reported in several places
- Hard
- L3
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Given a string s and a list of dictionary words, put spaces into s to build every sentence in which each word comes from the dictionary. A word can be used any number of times. For example, s = "catsanddog" with the words cat, cats, and, sand, dog gives "cat sand dog" and "cats and dog". The string has up to 20 characters, and the dictionary has up to 1,000 words of length up to 10.
Restated in our own words, not a quote from Google or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: can a dictionary word be reused? (Yes, the prompt says so.) Does the dictionary contain duplicates? Can s be empty? What do I return when no sentence exists? In what order do you want the sentences? And how large can the output get? With 20 characters there are 19 gaps, and each gap either holds a space or not, so at most 219 sentences exist.
Assumptions I would state: s has at least one character, I treat the dictionary as a set, no valid split means an empty list, and I return the sentences sorted so the answer has one canonical order.
Brute force
Say the obvious answer and why it is too slow.
The plain solution is backtracking. At each position try every dictionary word that matches there, move forward by its length, and recurse. When the end is reached, record the sentence. It is correct and short.
It has no memory. Many different prefixes lead to the same position, and each one re-solves the same suffix from scratch. Worse, it keeps doing this on suffixes that can never succeed. Take a string made of "cat" repeated many times and ending in "cow", with the words Cat, Ca and t: every way to split the repeated part is explored, only to find at the end that "cow" cannot be built, and the answer is empty. The number of explored paths doubles with each extra "cat", which is a lot of work for an empty answer. Work is spent on dead ends again and again.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(2ⁿ) even when no answer exists
- Time
- O(n·L²) plus building and sorting the sentences; exponential in n at worst
- Space
- O(total size of the cached sentences); exponential in n at worst
The pattern is memoised backtracking, which is top-down DP over the starting index of a suffix. Define sentencesFrom(start) as the list of every sentence that can be built from s[start..]. If start equals the length of s, there is exactly one sentence, the empty one. Otherwise try each end position: if s[start..end) is a dictionary word, put that word in front of every sentence from sentencesFrom(end).
The key observation is that the answer for a suffix depends only on where it starts, never on how we got there. So there are only n + 1 different subproblems, and we cache each result in a map. A dead end is cached too, as an empty list, so a hopeless suffix is explored once instead of once per prefix that reaches it.
Why is it correct and free of duplicates? Every sentence has exactly one first word, and what remains is a sentence of the suffix after it. So grouping sentences by their first word splits the answer into disjoint parts with nothing missing. I also stop the end position at the longest dictionary word, so I never slice strings that are too long to match.
One honest caveat for the interviewer: the output itself can be exponential ("aaaa..." with the words a, aa and aaa has about 1.84n sentences, because each length can be written as a sum of 1s, 2s and 3s in many ways), so no algorithm can be polynomial in the worst case. Memoisation makes the cost proportional to what is built, not to the number of dead paths.
Walk it through
A dry run on the example, step by step.
| Step | Start | Word tried | What happens | Cached result |
|---|---|---|---|---|
| 1 | 0 | cat | recurse to index 3 | - |
| 2 | 3 | sand | recurse to index 7 | - |
| 3 | 7 | dog | reaches the end | 7: [dog] |
| 4 | 3 | sand | rest is dog | 3: [sand dog] |
| 5 | 0 | cat | rest is sand dog | partial: cat sand dog |
| 6 | 0 | cats | recurse to index 4 | - |
| 7 | 4 | and | index 7 is in the cache | 4: [and dog] |
| 8 | 0 | cats | rest is and dog | 0: both sentences |
Take s = "catsanddog". The table lists the calls in the order they finish. From index 0 the word "cat" leads to index 3. From index 3 the word "sand" leads to index 7, and from 7 the word "dog" reaches the end, so index 7 stores the single sentence "dog". Index 3 then stores "sand dog", and index 0 gets its first sentence, "cat sand dog".
Back at index 0 the word "cats" leads to index 4. From 4 the word "and" leads to index 7, which is already in the cache, so no work is repeated: index 4 stores "and dog". Index 0 now holds the second sentence, "cats and dog". After sorting, the answer is "cat sand dog" followed by "cats and dog".
The code
Runnable JavaScript, checked against test cases.
function wordBreak(s, wordDict) {
const words = new Set(wordDict);
const longest = Math.max(0, ...wordDict.map((word) => word.length));
const cache = new Map();
function sentencesFrom(start) {
if (start === s.length) return [""];
if (cache.has(start)) return cache.get(start);
const sentences = [];
const lastEnd = Math.min(s.length, start + longest);
for (let end = start + 1; end <= lastEnd; end++) {
const word = s.slice(start, end);
if (!words.has(word)) continue;
for (const rest of sentencesFrom(end)) {
sentences.push(rest === "" ? word : word + " " + rest);
}
}
cache.set(start, sentences);
return sentences;
}
return sentencesFrom(0).sort();
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No valid split: for "catsandog" some indices store an empty list and the final answer is an empty list.
- Word longer than the string: the end position never goes past the string, so it is never tried.
- Empty dictionary: the longest length is 0, the loop does not run, and the result is empty. Using
Math.max(0, ...)avoids a result of negative infinity. - Reused words: nothing is removed from the dictionary, so "a a a" is allowed.
- Duplicate dictionary entries: building a Set removes them, otherwise sentences would repeat.
- Whole string is one word: the sentence is just that word, with no leading or trailing space.
- Huge output: allowed, and unavoidable.
Follow-ups to expect
Where the interviewer pushes next.
- How would a yes-or-no Word Break check, run first, help you skip impossible inputs quickly?
- How would you only count the sentences instead of listing them, and what does it cost?
- How would a trie of the dictionary replace the slice-and-lookup step?
- How would you return only the sentence with the fewest words?
- What if each word has a cost and you want the cheapest sentence?
Where candidates slip
The mistakes this problem punishes.
The biggest slip is writing plain backtracking and calling it done. It passes the small example and then times out on a long repeated string whose last piece is not in the dictionary.
- Caching only the successes, so dead-end suffixes are recomputed.
- Joining words with a space and leaving a stray space at the front or the end of a sentence.
- Pushing into a cached list that another call is still reading.
- Looping the end position past the longest word, which wastes time slicing.
- Answering with a boolean DP table from Word Break I, which tells you whether a split exists but not what the splits are.
- Forgetting that the result order is unspecified, so tests only pass after sorting.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.