题目(leecode T131):
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串。返回 s
所有可能的分割方案。
方法:本题是一个分割回文串的问题,是回溯算法的另一类问题。 针对一个字符串,我们要对其进行分割,并且确保分割后生成的子串也必须全都是回文串。分析回溯三部曲
1:传入参数与返回值:传入字符串s,以及切割的起始位置startIndex,不需要返回值
2:终止条件:因为切割位置startIndex控制的是切割的起始位置,当startIndex大于等于s.size时,就意味着已经切到了最后,也就该停止了。
3:单层处理逻辑:在单层中我们需要从字符串中截取子串。
在for (int i = startIndex; i < s.size(); i++)
循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文,如果是回文,就加入在vector<string> path
中,path用来记录切割过的回文子串。
题解:
class Solution {
private:
vector<string> path;
vector<vector<string>> result;
void backtracking(const string& s,int startIndex){
if(startIndex >= s.size()){ //终止条件
result.push_back(path);
return;
}
for(int i = startIndex; i < s.size(); i++){
if(isPalindrome(s, startIndex, i)){
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
}else{
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程,弹出本次已经添加的子串
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};