Word Break II

I picked this up while doing a Microsoft principal-engineer loop refresh and the first time I wrote it, I built a forwards DP that returned a boolean[] and then re-walked it to enumerate sentences. That was ugly. The clean solution is memoized DFS keyed by START index, where solve(start) returns the list of sentence-suffixes from start and the parent stitches them with the matched prefix word. The catalog covered word-break (the boolean version), but it skipped this enumeration variant where memoization HAS to remember lists of strings, not booleans.

Word Break II

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. The same dictionary word may be reused multiple times in the segmentation.

Examples

Example 1:

• Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
• Output: ["cats and dog", "cat sand dog"]
• Explanation: Two valid segmentations.

Example 2:

• Input: s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
• Output: ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]
• Explanation: Three valid segmentations.

Example 3:

• Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
• Output: []
• Explanation: No segmentation produces only dictionary words.

Example 4:

• Input: s = "a", wordDict = ["a"]
• Output: ["a"]
• Explanation: Single-word string with the trivial split.

Constraints

• 1 <= s.length <= 20.
• 1 <= wordDict.length <= 1000.
• 1 <= wordDict[i].length <= 10.
• s and wordDict[i] consist only of lowercase English letters.
• All the strings in wordDict are unique.
• Input is generated such that the length of the answer doesn't exceed 10^5.

Follow-up

Why is the bottom-up boolean DP O(n^2) but this enumeration variant exponential in the worst case? The boolean version answers a single yes/no question per index, so memoization shrinks the state to O(n). The enumeration must materialize EVERY sentence, and an input like "aaaaaa..." with wordDict = ["a", "aa"] has Fibonacci-many segmentations. Memoization avoids recomputing them but cannot avoid emitting them; the output size dominates.