Word Break II
Word Break II: return every sentence formed by splitting a string into dictionary words.
- 1 <= s.length <= 20
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 10
- s and wordDict[i] consist of only lowercase English letters.
- All the strings of wordDict are unique.
- Input is generated in a way that the length of the answer doesn't exceed 10⁵.
Intuition
Word break ii returns every sentence formed by splitting a string into dictionary words — the enumeration version of Word Break, which only asks whether a split exists.
Plain backtracking explores every cut, and it wastes work in a specific way. Many different prefixes lead to the same position in the string, and from that position the set of possible completions is identical regardless of how you arrived:
- The sentences constructible from index i depend only on i, never on the path taken to reach it.
That is the memoisation condition, and it is the same observation that turns Word Break from exponential to linear. The difference is what gets cached: Word Break stores a boolean per index, while this problem stores the list of sentences for each index.
So define build(start) as every sentence forming the suffix from start. Try each prefix that is a dictionary word, recurse on what follows, and prepend the word to each returned sentence. Cache the finished list.
The base case is the one to get right. At the end of the string, return a list containing one empty sentence — not an empty list. An empty list means no completions exist, which would kill every branch; a list with one empty element means the suffix is complete, giving the final word something to attach to.
Worth being honest about the bound: memoisation removes duplicated work but the output itself can be exponential, since a string like "aaaa" with ["a", "aa"] has exponentially many valid sentences.
A request to return all segmentations combines backtracking for enumeration with DP for repeated suffixes. Memoize complete result lists by starting index rather than only whether a suffix is possible.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n^2 + output size) time and O(n + output size) space.
Define the state as a suffix index
build(start) returns every sentence forming s[start:]. The completions depend only on the index, which is what makes caching valid — the same observation that powers the simpler Word Break.
Return one empty sentence at the end
When start reaches the string's length, return a list containing a single empty string. An empty list would mean no completions exist and would silently discard every valid branch — this distinction is the most common bug here.
Try only dictionary prefixes
For each end position, take s[start:end] and continue only if it is in the word set. Each recursive step therefore corresponds to committing to one real word, and invalid prefixes are pruned before any recursion.
Prepend the word to each completion
For every sentence returned by build(end), produce word + ' ' + suffix, or just word when the suffix is empty. Handling the empty case separately is what avoids a trailing space on the final word.
Cache the completed list
Store the finished list for start before returning it. Many different earlier splits reach the same index, and without the cache each one re-derives the identical set of completions.
Use a set for the dictionary
Membership tests run inside the inner loop, so a hash set gives O(1) lookups. Bounding the loop by the longest word length avoids testing substrings that could never match.
Cost of the memoised enumeration
Memoisation removes repeated work, but the output itself can be exponential — "aaaa" with ["a", "aa"] yields exponentially many sentences. Time is O(n² · number of results) with O(n · results) space; no algorithm can beat the output size.
Solution & live demo
Common pitfalls
Returning no completion at the string end
if start == len(s):
return []if start == len(s):
return ['']The caller needs one neutral completion to emit its final chosen word.
Always appending a space
sentences.append(word + ' ' + suffix)
sentences.append(word if not suffix else word + ' ' + suffix)
The terminal empty suffix would otherwise create trailing whitespace.
Caching only booleans
memo[start] = can_break
memo[start] = sentences
The output requires every actual sentence, not merely feasibility.
Edge cases
Every branch returns an empty list, so the final result is empty.
The empty-suffix base case yields that word without a trailing space.
Memoization constructs that suffix's sentences once and reuses them.