Word Break II
HardProblem Description
Given a string s and a dictionary of strings wordDict, add spaces in s to construct all possible sentences where each word is in wordDict.
Return all such possible sentences in any order.
For this live runner, return sentences in sorted lexicographic order for deterministic checking.
Examples
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cat sand dog","cats and dog"]
Example 2:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
Constraints
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10
Hint
Memoized DFS avoids recomputing suffix solutions.
Solution
Test Results
Run tests to see the overall score, band, and section breakdown.
Public Tests
Detailed feedback for visible cases.
Public test details will appear here after you run your solution.
Hidden Tests
Summary only, with no hidden inputs or outputs.
Performance
Execution timing and pass/fail status.
No performance results yet.
AI Interviewer
I'll review your code once you submit it. I can also give you hints if you get stuck!