LeetCode 131 分割回文串 - 回溯解法
https://leetcode.cn/problems/palindrome-partitioning/description/
思路
手动模拟
s = “aab”
先切为 [a, ab]：左边是回文串；右边继续切 "ab"，可切为 [a, b]，也都是回文串。
先切为 [aa, b]：左边是回文串，右边也是回文串。
每次都先切出左侧一段，再递归处理右侧。
对于 “aaba”
[a, aba] 这种情况不会遗漏，因为切分位置可以放到最右侧，此时右侧为空串。
为什么不一开始在最左侧切，让右侧保持完整 aba？因为如果允许左侧为空，path 的处理要额外加判断逻辑。
错误代码
for(从每个位置切){
if 左边是回文串{
path.push(左边)
qie(右边)
path.pop()
}
}
这里还没有返回
返回的逻辑
if(s.size()==1){
path.push_back(s);
result.push_back(path);
return;
}
这里是错误的：在返回分支中执行了 `path.push`，但没有对应的 `pop`，会导致 `path` 残留脏数据。
path.push(左边)
qie(右边)
path.pop()
按理来说这里 `pop` 的应该是左边片段，但由于前面的返回分支额外执行了 `push`，这里 `pop` 的反而是刚才 `return` 分支压入的 `s`，会导致结果错误。
对于 "aab"
输出是 [["a","a","b"],["a","aa","b"]]
可以看到最里面的 `a` 没有被正确弹出。
解决方式：不要在返回分支执行 `path` 的 `push/pop`。因此终止条件改为“字符串为空时保存结果并返回”，而不是“长度为 1 时处理”。
class Solution {
public:
vector<vector<string>> result;
vector<string> path;
bool is_huiwen(string s){
for(int i = 0, j = s.size()-1;i<=j;i++,j--){
if(s[i]!=s[j])return false;
}
return true;
}
void qie(string s){
if(s.size()==1){
path.push_back(s);
result.push_back(path);
return;
}
for(int i = 1;i<=s.size();i++){
string left = s.substr(0,i);
string right = s.substr(i,s.size()-i);
if(is_huiwen(left)){
path.push_back(left);
qie(right);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
qie(s);
return result;
}
};
正确代码
class Solution {
public:
vector<vector<string>> result;
vector<string> path;
bool is_huiwen(string s){
for(int i = 0, j = s.size()-1;i<=j;i++,j--){
if(s[i]!=s[j])return false;
}
return true;
}
void qie(string s){
//遍历完所有情况, 右侧为空, 传入s为空, 此时返回
if(s.size()==0){
// path.push_back(s);
result.push_back(path);
return;
}
for(int i = 1;i<=s.size();i++){
string left = s.substr(0,i);
string right = s.substr(i,s.size()-i);
if(is_huiwen(left)){
path.push_back(left);
qie(right);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
qie(s);
return result;
}
};
理解
做完后的理解， 一开始这个问题一直没有找到一个不变的流程，但后面想到了:
从串的前面(遍历式)截下来一个回文串并加到path中，不断地重复直到串为空.
仍然是往path中加值.
这个不变的流程是 函数的语义: 从串的前面不断切出回文串
if(s为空){
result保存, 返回
}
for(遍历切割位置){
切下来的左边为回文串{
左边加入到path
qie(右边)
path pop
}
}