127. Word Break II
HardBacktracking
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**. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Examples
Input: catsanddog ["cat","cats","and","sand","dog"]
Output: ["cat sand dog","cats and dog"]
Explanation: Two valid segmentations of catsanddog.
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.
Loading...
Run checks all cases above. Submit evaluates all test cases.