第九十九天 --- 力扣140. 单词拆分 II
题目一
力扣:140. 单词拆分 II
思路
1、这很明显，是一种维护出所有符合要求的路径的问题，这种问题在大方向上一定要明确，首选就是——————>“回溯法”
2、我们分两种方法介绍，第二种是优化版本，建议使用第二种方法。
一：不含“记忆化”优化的回溯
1、这个算法的核心思想就是，自己干自己的，每个分支我都单独给你一个维护的串，等维护到最后符合要求者直接进入答案种。
2、每一次都从point处(这个是我代码里的名词，大家可以先带着疑惑继续看下去，在代码中我会给出解释)，向后扫描他自己维护的串，从point到此处一旦这个字串是在字典中的(说明在这里可以分割)，用临时串做出相应变化后传入下一个递归函数种，单独进行一个分支的寻找，等分支结束之后本函数继续向后找(因为可能有多种分割方法，后面还可能有别的分割点和之前的分支是相互独立的，所以继续找下去)，直到串遍历结束即可。
3、对2的补充：“point”代表了，这个点之前的部分已经找好了，我们这次从这个点之后继续
细节：
1、每个递归函数都要维护一个自己的串，在参数中。
2、参数中还要维护当前分支从何处开始继续找，是point;因为加了空格，所以串的总长会变，所以用size维护当前串的总长度。
3、成功的串，最后一定会多一个空格，因为在分析到最后一个字符时候，判断在字典中，所以会加一个空格，所以最后在答案里面要去掉。
二：“记忆化”优化回溯
为什么要优化？
你仔细的分析上面的方法：
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
这个样例中，当在"cat"处进行分割之后，会走过一遍dog的位置，也就是说，后面的部分他经过了一遍；
当在"cats“处分割了，也一样会经过dog处，那得到的结果不是和上面一样的吗，这样就造成了重复运算，所以我们采用记忆化的方式来优化，减少无意义的重复运算。
过程
1、总体思路和上面的方法无异。
2、但是我们要想一个办法把走过的地方记录下来，不能让他跑完这一趟白跑了，反复地做无意义的重复工作！(这也和我们学习一样，不能熊瞎子掰苞米，边学边扔)
3、那么，我们就换一种思路进行答案的存取，说实话我上一个方法，并不是纯粹的回溯，因为并没有真正的带回什么东西，所以我们让他带回来东西。
4、做一个大过程，开始就做一个事->分割。从前到后找，找到了目标，就进入递归函数，把point(和上面解释一样)传下去，如果传的位置恰好是s.size()，说明，恰好是在最后一个字符处又找到了字典中的单词(最后一个字符是s.size()-1，传递的时候位置会++)，那么这种分解就是有效的，并创建空串，用户回溯拼接之前的分解结果
5、我们分割完了开始回溯，这时候关键就来了，我们用一个unordered_map来存储各个点的vector ，等子过程返回了，说明子过程找全了，那么我们就用子过程的unordered_map的vector，把自己那部分拼好，存在map种自己对应的位置上。
6、等到回到第一个元素的位置上，都拼接完了之后，就是答案。
SumUp：一句话，就是从上到下逐层分解，成功，就开一个空串，再逐层返回一点点添加，直到回到最顶层，用这种方式的回溯，是可以存储每个分支点处的情况的，减少了重复计算。
细节
1、有了上述过程，那么谁起到了优化过程呢，就是当我们分下去一个字过程的时候，就得查map中有没有与之对应的记录，有，直接返回即可，不用再找了。
2、关于1中方法的正确性，其实也好证明，比如在i处分割出的子过程，在回溯过程返回时候，i后面所有可能就都走过了，所以咋访问i的时候，直接用记录就行。
代码
一
class Solution {
public:
unordered_set<string> item;
vector<string> ans;
string s;
void dfs(string tmp, int point, int size) {//维护一个答案，从何处开始分析，该串大小
if (point == size) {//走到最后
if (tmp[tmp.size() - 1] == ' ') {//最后有空格代表是答案
tmp.erase(tmp.size() - 1);
ans.push_back(tmp);
}
return;
}
int cur = point;
while (cur < size) {//从起点开始向后走，直到末尾
string this_str = tmp.substr(point, cur - point + 1);
if (item.count(this_str) > 0) {//在字典里
string ttmp = tmp;
ttmp.insert(cur + 1, " ");
dfs(ttmp, cur + 2, size + 1);//第二个参数主要是加了空格，得越过空格，所以+2
}
cur++;
}
return;
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
this->s = s;
for (string tmp : wordDict) {
item.insert(tmp);
}
dfs(s, 0, s.size());
return ans;
}
};
所有代码均以通过力扣测试
（经过多次测试最短时间为）：
二
class Solution {
public:
unordered_set<string> item;
unordered_map<int, vector<string>> ans;
string s;
int size;
void dfs(int index) {
if (!ans.count(index)) {//这里做出了优化，只有之前没出现过的字符才会被继续求，反之直接用老本
if (index == this->size) {//这种经典回溯，先逐层分解，再随着函数返回逐渐添加即可。
ans[index] = { "" };//成功走到最后，开一个空串，边回溯边添加
return;
}
ans[index] = {};//起码这里是个断开的点，如果是正好完成了整个句子的搜索，那么返回的空串，不然，这里也得是先开好，准备把后面来的串加上
int cur = index;
while (cur < this->size) {
string str = s.substr(index, cur - index + 1);
if (item.count(str) > 0) {//成功找到字典中的单词
dfs(cur + 1);
for (string tmp : ans[cur + 1]) {
ans[index].push_back(tmp == "" ? str : str + " " + tmp);
}
}
cur++;
}
return;
}
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
this->s = s;
this->size = s.size();
for (string tmp : wordDict) {
item.insert(tmp);
}
dfs(0);
return ans[0];
}
};
所有代码均以通过力扣测试
（经过多次测试最短时间为）：
附加
其实这道题属于是被阉割了，最恶心的样例被砍掉了，所以这里建议读者自己进行一个超恶心的样例进行自测，不要相信他给你的测试结果。
“aaaaaaaaaaaaaaaaaaa”
[“a”,“aa”,“aaa”,“aaaa”,“aaaaa”,“aaaaaa”,“aaaaaaa”,“aaaaaaaa”,“aaaaaaaaa”,“aaaaaaaaaa”]
（我输出的结果顺序和标准的不一致，所以不必担心是算法有误）
方法一：
方法二：
可见相差的速度。