Word Break II
Hard · Dynamic Programming · String · Dynamic Programming · Backtracking · Memoization · Hash Table
Problem
You are given a string s and a list wordDict of distinct words. Add spaces to s so that every piece is a word from wordDict.
Return every sentence that can be made this way, in any order. A word may be used any number of times.
Examples
Input: s = "icecreamcone", wordDict = ["ice","cream","icecream","cone","creamcone"] Output: ["ice cream cone","ice creamcone","icecream cone"]
ice + cream + cone, ice + creamcone, and icecream + cone.
Input: s = "abcd", wordDict = ["ab","c"] Output: []
The final d is not part of any word, so there is no sentence.
Input: s = "gogo", wordDict = ["go","gog","o"] Output: ["go go","gog o"]
Either go + go, or gog + o. The word go is used twice in the first sentence.
Constraints
- 1 <= len(s) <= 20
- 1 <= len(wordDict) <= 1000
- 1 <= len(wordDict[i]) <= 10
- s and every word contain only lowercase English letters
- all words in wordDict are distinct
- the total length of all answers is at most 10^5
Approaches
- Baseline: backtracking without a cache — time O(2^n · n) worst, space O(n) besides the output
Follow-up
If you only need to know whether a split exists, or how many there are, a boolean or a count per suffix is enough and the work becomes polynomial; the use cases below ask both. Listing every sentence cannot beat the size of the output, which can grow exponentially with the length of s, which is why s is kept short here.
Related problems
Start free on Cariara · Coding problems · System design studio
