Description
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.
Examples
Input:
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]Output:
["cats and dog","cat sand dog"]Explanation:
Two valid segmentations.
Input:
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]Output:
["pine apple pen apple","pineapple pen apple","pine applepen apple"]Explanation:
Three valid segmentations exist: 'pine apple pen apple' uses individual words, 'pineapple pen apple' uses the compound word 'pineapple', and 'pine applepen apple' uses the compound word 'applepen'. This demonstrates overlapping word boundaries and compound words.
Input:
s = "abcd", wordDict = ["a","abc","b","cd"]Output:
["a b cd"]Explanation:
Only one valid segmentation is possible. Although 'abc' exists in the dictionary, using it would leave 'd' which cannot be formed from the remaining dictionary words. This shows how greedy matching of longer words doesn't always work, requiring backtracking to find valid solutions.
Constraints
- •
1 ≤ s.length ≤ 20 - •
1 ≤ wordDict.length ≤ 1000