# 单词拆分 II
给定一个非空字符串 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
```java
class Solution {
public List wordBreak(String s, List wordDict) {
List res = new ArrayList<>();
int max = 0, min = Integer.MAX_VALUE;
Set set = new HashSet<>();
for (String word : wordDict) {
set.add(word);
max = Integer.max(max, word.length());
min = Integer.min(min, word.length());
}
boolean f[] = new boolean[s.length() + 1];
f[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
for (int j = Math.max(i - max, 0); j <= i - min; j++) {
if (f[j] && set.contains(s.substring(j, i))) {
f[i] = true;
break;
}
}
}
if (f[s.length()]) {
dfs(s, res, new StringBuilder(), set, 0, max, min);
}
return res;
}
private void dfs(String s, List res, StringBuilder sb, Set set, int index, int max, int min) {
if (index == s.length()) {
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
return;
}
String str;
int size;
for (int i = index + min; i <= s.length() && i <= index + max; i++) {
if (set.contains(str = s.substring(index, i))) {
size = sb.length();
sb.append(str).append(' ');
dfs(s, res, sb, set, i, max, min);
sb.delete(size, sb.length());
}
}
}
}
```
## 答案
```java
```
## 选项
### A
```java
```
### B
```java
```
### C
```java
```