LeetCode #140 Hard

Word Break II

Return every sentence formed by splitting a string into dictionary words.

stringbacktrackingmemoization

02

Intuition

Trying every cut generates many dead branches and recomputes sentences for the same suffix. Once a prefix word is selected, every completion depends only on the index immediately after it. Memoize the list of sentences constructible from each starting index. Combining the chosen word with each cached suffix produces all valid sentences without duplicate subproblem work.

How to spot this pattern

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.

03

Approach

1

Search sentences from a suffix boundary

Define build(start) as every space-separated sentence that forms s[start:]. At the end of the string, return a list containing the empty sentence so a final word has one valid completion to attach to.

2

Try only dictionary prefixes

For each possible end position, inspect s[start:end] and continue only if that substring belongs to the word set. This makes each recursive step correspond to one legal word.

3

Combine words with cached suffix sentences

For every sentence returned from build(end), append either word + ' ' + suffix or just word when the suffix is empty. Cache the completed list for start because many earlier splits may reach it.

04

Solution

▶1class Solution:
▶2    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
▶3        words = set(wordDict)
▶4 
▶5        @cache
▶6        def build(start):
▶7            if start == len(s):
▶8                return ('',)
▶9            sentences = []
▶10            for end in range(start + 1, len(s) + 1):
▶11                word = s[start:end]
▶12                if word in words:
▶13                    for suffix in build(end):
▶14                        sentences.append(word if not suffix else word + ' ' + suffix)
▶15            return tuple(sentences)
▶16 
▶17        return list(build(0))

05

Common pitfalls

Returning no completion at the string end

✗ Wrong

if start == len(s):
    return []

✓ Right

if start == len(s):
    return ['']

The caller needs one neutral completion to emit its final chosen word.

Always appending a space

✗ Wrong

sentences.append(word + ' ' + suffix)

✓ Right

sentences.append(word if not suffix else word + ' ' + suffix)

The terminal empty suffix would otherwise create trailing whitespace.

Caching only booleans

✗ Wrong

memo[start] = can_break

✓ Right

memo[start] = sentences

The output requires every actual sentence, not merely feasibility.

06

Edge cases

No complete segmentation exists

Every branch returns an empty list, so the final result is empty.

One dictionary word covers the whole string

The empty-suffix base case yields that word without a trailing space.

Several splits share the same suffix

Memoization constructs that suffix's sentences once and reuses them.

07

Complexity

Time

O(n^2 + output size)

Space

O(n + output size)

Substring checks examine candidate cuts while returned sentences necessarily consume output-proportional space.