给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
示例 1：
输入: s = "catsanddog" wordDict =["cat", "cats", "and", "sand", "dog"]输出:[ "cats and dog", "cat sand dog" ]
示例 2：
输入: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] 解释: 注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: []## template ```python class Solution(object): def dfs(self, low, length, s, res, vaild, path=[]): if low == length: res.append(" ".join(path)) return for i in range(low, length): if vaild[low][i]: self.dfs(i + 1, length, s, res, vaild, path + [s[low : i + 1]]) def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: List[str] """ length = len(s) vaild = [[False] * length for _ in range(length)] dp = [False for _ in range(length + 1)] dp[0] = True wordDict = set(wordDict) for i in range(1, length + 1): for j in range(i + 1): word = s[j:i] if dp[j] and word in wordDict: dp[i] = True vaild[j][i - 1] = True res = [] if dp[-1]: self.dfs(0, length, s, res, vaild) return res ``` ## 答案 ```python ``` ## 选项 ### A ```python ``` ### B ```python ``` ### C ```python ```