每日一题 分割回文串（深度优先搜索）
131. 分割回文串
Difficulty: 中等
给你一个字符串 s，请你将s分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
-
1 <= s.length <= 16 -
s仅由小写英文字母组成
题目分析
题意应该都清楚了，把一个字符串分割成若干回文串。希望你返回所有的分配方法。然后呢，让我们一点点拨茧抽丝一下这个问题：
-
由于单个字符构成的字符串是回文串，所以这道题不存在无解的情况。
-
如果字符串所有字符都是一样的，那么最后的可能情况应该为$2^{s.length()-1}$。此时我去看了一眼数据范围，字符串长度最长为16，时间复杂度可以承受。
-
该问题是具有递归性质的，s的所有回文分割可以由s所有后缀的回文分割得到。看下面这张图，代表了aabb的回文分割。
-
每条边代表删除的回文前缀。最后的分割方案，就是从aaba到空字符串的所有路径。从这张图中，我们可以看出，这个问题不仅可以通过递归解决，还具有 公共子问题的特性，因此必然也能使用带记忆的搜索。
问题分析完毕，下面是代码，然而我是一条咸鱼，既然直接搜索能过这道题，就不写记忆化了。
Solution
Language: c++
class Solution {
public:
// 功能函数，判断一个字符串是否为回文
bool isPalindrome(string s){
for (int i = 0, j = s.length()-1; i < j; i++, j--){
if (s[i] != s[j])
return false;
}
return true;
}
vector<vector<string>>dfs(string s){
// 如果字符串为空，返回唯一的分配方案，
// 即一个空集
if (s == "") return {{}};
vector<vector<string>> ret;
// 依次遍历前缀
for (int i = 1; i <= s.length(); i++){
string subs = s.substr(0, i);
// 如果该子串为回文
if (isPalindrome(subs)){
// 获取剩余部分的字串分割方案
auto parts = dfs(s.substr(i));
// 把剩余部分的字串分配方案，
// 加上当前字串，并合并答案
for (auto& p: parts){
p.push_back(subs);
ret.push_back(p);
}
}
}
return ret;
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ret = dfs(s);
// 写法问题，由于我的写法类似于后序遍历，因此需要将所有答案反过来
for (auto& p: ret)
reverse(p.begin(), p.end());
return ret;
}
};