Problem Statement
Given a string s and a dictionary of words wordDict, add spaces in s to construct all possible sentences such that every word is a valid word in wordDict. Return all such possible sentences in any order.
🔹 Example 1:
Input:
s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
["cats and dog", "cat sand dog"]
🔹 Example 2:
Input:
s = "pineapplepenapple" wordDict = ["apple","pen","applepen","pine","pineapple"]
Output:
["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]
⚙️ Approach (Explanation)
This is a backtracking + memoization (DP) problem.
-
We recursively try to break the string at every possible point.
-
If a substring exists in the dictionary, we recursively solve for the remaining part.
-
To avoid re-computation, we store results of subproblems in a HashMap (memoization).
-
Finally, we join all combinations that form valid sentences.