大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个字符串s和字符串列表wordDict作为字典，在字符串s中增加空格来构建一个句子，使得句子中所有的单词都在词典中，以任意顺序返回这些句子。”
2、题目描述
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。
示例 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"] 解释: 注意你可以重复使用字典中的单词。
二、解题
1、思路分析
这道题是139题的进阶，139题要求判断是否可以拆分，这道题要求返回所有可能的拆分结果。
139题使用了动态规划思路来判断是否可以拆分，这道题也可以使用动态规划思路，但是如果使用动态规划从下向上拆分，无法提前判断是否可以拆分，在不能拆分的时候会超时。
那么可以使用记忆化搜索，在搜索过程中将不可以拆分的情况进行剪枝。
那么记忆化搜索具体怎么做的？
首先，使用一个哈希表存储字符串s的每个下标和从该下标开始的部分组成的句子列表。
在回溯的过程中，如果遇到已经访问过的下标，可以直接从哈希表中得到结果，不需要重复计算；
如果某个下标无法匹配，则哈希表中该下标对应的是空列表，因此可以对不可以拆分的情况进行剪枝。
2、代码实现
代码参考：
class Solution { public List<String> wordBreak(String s, List<String> wordDict) { Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>(); List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map); List<String> breakList = new LinkedList<String>(); for (List<String> wordBreak : wordBreaks) { breakList.add(String.join(" ", wordBreak)); } return breakList; } public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) { if (!map.containsKey(index)) { List<List<String>> wordBreaks = new LinkedList<List<String>>(); if (index == length) { wordBreaks.add(new LinkedList<String>()); } for (int i = index + 1; i <= length; i++) { String word = s.substring(index, i); if (wordSet.contains(word)) { List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map); for (List<String> nextWordBreak : nextWordBreaks) { LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak); wordBreak.offerFirst(word); wordBreaks.add(wordBreak); } } } map.put(index, wordBreaks); } return map.get(index); } }
3、时间复杂度
时间复杂度：
时间复杂度为指数级别，无法进行具体分析。
空间复杂度：
空间复杂度为指数级别，无法进行具体分析。
三、总结
对于字符串s 拆分后组成句子，可以有很多种拆分方法，这些其实不是最终答案，但是在记忆化搜索过程中这些结果都会存下来。
这一部分占用的空间至少有O(n * 2n)，其实n是字符串的长度，也就是分割方法有2n，每一种方法需要O(n)的字符串进行存储。
对于时间复杂度来说，写入O(n * 2n)空间至少也需要O(n * 2n)的空间，因此时间复杂度同样也是指数级。
