前言
回溯章节第六篇。切割问题。
记录 六十八【131.分割回文串】。
一、题目阅读
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。回文串指字符串从前读和从后读一样。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
二、尝试实现
思路
- 分析题目：输出结果元素是一种完整的分割方案。和字符串章节找回文串有区别。
- 在记录 六十三【回溯章节开篇】中说切割问题也是用回溯解决。并且回溯一定可以构造树形结构，从树形结构，结合前五篇解决组合问题的经验入手。
- 以示例1建立树形结构，宽度是字符串的分割点，深度是字符串的长度。
- 对照树形结构写递归函数：
- 确定返回值：肯定是void类型；
- 确定参数：
- int startindex 代表每一层可选分割点的起始位置。类似组合问题中的startindex，每一层从哪些元素中开始选取；比如：startindex=0，指s[0]字符后的分割点；startindex = 1，指s[1]字符后的分割点。
- string& s 代表输入的字符串。
- 确定终止条件：当startindex == s.size()代表字符串已经分割结尾时，把temp放入result中，return；
- 确定单层逻辑：
- for循环：i从startindex开始，i指定某个下标后的分割点。传给下一层，应该从i+1开始。i < s.size()；
- 确定i之后，先把子串用s.substr函数返回。传入第一个参数是起始位置，第二个参数是长度。
- 判断这个子串是回文串吗？用reverse反转之后比较是否相等。如果不是，continue，不再深入递归；如果是回文串，放到temp中，递到下一层。
- 回溯操作：把该层放入temp的子串pop，进入下一轮i。
代码实现
class Solution {
public:
vector<vector<string>> result;//最终的返回值
vector<string> temp;//中间结果
void backtracking(int startindex,string& s){
//终止条件,一种分割方案完毕
if(startindex == s.size()){
result.push_back(temp);
return;
}
//递归
for(int i = startindex;i < s.size();i++){
//获得子串
string sstr = s.substr(startindex,i-startindex+1);//第一个参数是起始位置，第二参数是长度
string r_sstr = sstr;
reverse(r_sstr.begin(),r_sstr.end());
if(sstr != r_sstr){//判断该子串是回文串吗？
continue;//剪枝
}
temp.push_back(sstr);//放入该子串
backtracking(i+1,s);//递到下一层
temp.pop_back();//回溯
}
return;
}
vector<vector<string>> partition(string s) {
result.clear();
temp.clear();
backtracking(0,s);
return result;
}
};
三、参考学习
学习内容
- 使用回溯的思路是正确的。回溯使用特点：在一个集合中进行切割。
- 解决两个问题：1. 切割方案；2. 判断回文。参考代码实现和二、代码实现对比：
- 细节一：递归函数参数string& s改成const string& s，为了不对s进行修改，一旦有修改操作会警告。
- 细节二：终止条件——参考给startIndex >= s.size()；个人写startIndex == s.size()；这两个都可以。
- 细节三：参考使用双指针另外写了一个函数调用来判断是否是回文串。而个人在reverse两行完成判断操作。
-
优化方法：用动态规划提前知道string s中的任何子串是否是回文串。没学到动态规划，但是先接触一下，从函数中分析动态规划的过程：
void computePalindrome(const string& s) { // isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串 isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); // 根据字符串s, 刷新布尔矩阵的大小 for (int i = s.size() - 1; i >= 0; i--) { // 需要倒序计算, 保证在i行时, i+1行已经计算好了 for (int j = i; j < s.size(); j++) { if (j == i) {isPalindrome[i][j] = true;} else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);} else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);} } } }这是动态规划的函数。其中isPalindrome是二维矩阵，类型是：vector< vector< bool>>。如下图，一个举例。
总结
（欢迎指正，转载标明出处）