给定一个非空字符串 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"]
输出:
[]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break-ii
着作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：要注意先利用单词拆分I的方法判断是否能够拆分，这样才不会超时。
单词拆分I :https://blog.csdn.net/weixin_43981315/article/details/109426338
使用哈希表存储字符串 s 的每个下标和从该下标开始的部分可以组成的句子列表，在回溯过程中如果遇到已经访问过的下标，则可以直接从哈希表得到结果，而不需要重复计算。如果到某个下标发现无法匹配，则哈希表中该下标对应的是空列表
class Solution {
List<String> res;
public boolean wordBreak2(String s, List<String> wordDict) {
int len=s.length();
boolean dp[]=new boolean[len+1];
dp[0]=true;
for(int i=0;i<len;i++){
for(int j=0;j<=i;j++){
if(dp[j]==true&&wordDict.contains(s.substring(j,i+1)))
dp[i+1]=true;
}
}
return dp[len];
}
public List<String> wordBreak(String s, List<String> wordDict) {
res=new ArrayList<>();
if(wordBreak2(s,wordDict)==false) return res;
Map<Integer,List<Integer>> map=new HashMap<>();
for(int i=0;i<s.length();i++){
for(int j=i+1;j<=s.length();j++){
//记录每一个i可以到达j的字符串
String tmp=s.substring(i,j);
if(wordDict.contains(tmp)){
List<Integer> list=map.getOrDefault(i,new ArrayList<Integer>());
list.add(j-1);
map.put(i,list);
}
}
}
dfs(map,0,new StringBuffer(),s.length(),s);
return res;
}
public void dfs(Map<Integer,List<Integer>>map,int index,StringBuffer buffer,int end,String s){
//回溯得到所有可能的拆分情况
if(index==end) res.add(buffer.toString());
if(index!=0) buffer.append(" ");/*增加空格*/
List<Integer> next=map.getOrDefault(index,new ArrayList<Integer>());
for(int i=0;i<next.size();i++){
String tmp=s.substring(index,next.get(i)+1);
buffer.append(tmp);
dfs(map,next.get(i)+1,buffer,end,s);
buffer.delete(buffer.length()-tmp.length()-1/*注意减掉空格*/,buffer.length());
}
}
}