Word Break II
The key idea
Treat it as a search: at each position, try every dictionary word that is a prefix of the remaining string, recurse on the suffix, and join the pieces. Memoize results by start index so shared suffixes are solved once instead of re-exploring exponentially.
Problem
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 word in the dictionary may be reused multiple times in the segmentation. Every character of s must belong to exactly one chosen word, and the chosen words, read left to right, must concatenate back to s.
Constraints
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare unique.
Examples
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
Complexity
Time: O(n * 2^n) Space: O(n * 2^n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM