DSA problem
Word Break II
Given a string s and a dictionary of strings wordDict, return all possible sentences that can be formed by inserting spaces between the words such that each fragment is a valid dictionary word. Words can be reused, and the order of the returned sentences does not matter.
This is the constructive sibling of the classic Word Break problem. Instead of merely asking whether s can be segmented, we must enumerate every valid segmentation. The natural approach is to recurse on suffixes: for a given index i, try every prefix s[i..j] that is in the dictionary, then recursively segment the suffix s[j+1..]. Concatenating each returned sentence with the chosen prefix yields one sentence for the current call.
Without care this enumeration is exponential. The optimization is memoization keyed by the start index (or equivalently the suffix). Once we know all sentences that segment s[i..], we can reuse them every time we hit position i from a different branch of the recursion. Combined with a hash-set lookup of the dictionary, the work per state is proportional to the number of sentences it produces plus the cost of slicing the prefix.
The worst-case output size is exponential, so the algorithm is still exponential in the worst case — that is intrinsic to the problem. In practice, memoization makes the typical input run quickly and prevents the recursion from doing duplicate work for the same suffix.
Examples
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]["cats and dog","cat sand dog"]s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]["pine apple pen apple","pineapple pen apple","pine applepen apple"]s = "catsandog", wordDict = ["cats","dog","sand","and","cat"][]Constraints
- 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 so the answer length is <= 10^5.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.