Hard
Quiz
#140 Word Break II
APPROACH
Given a string s and a dictionary wordDict, insert spaces into s to form sentences where every word exists in wordDict. Return all such sentences in any order.
Dictionary words may be reused multiple times within the same sentence.
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"]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
1 of 4
1:00
What is the optimal approach for this problem?