🖇 131.分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
思路
基本思想
开始第一想法是将一个字符串的所有分割结果列出来，统计其中所有的回文串，但是这种方法不符合题意，题目要求将字符串进行分割，分割的每一个子串都要求是回文串，而不是简单的从幂集中找出所有的回文串
所以需要使用回溯法进行搜索，当前子串是回文串，才能进行下一步分割，当前子串不是回文串，需要一直向后搜索，直到到了字符串末尾或者找到一个回文子串
一旦找到一个回文子串，剩下的部分就可以继续分割，继续分割可以使用回溯法，从当前位置的下一位置开始分割，也就是回溯法
当形成一个完整的分割方法时，分割位置走到了字符串的末尾，这是一个标志，代表着形成了一个完整的分割结果，因为只有前面的分割结果是回文串，才能对后面剩余的字符串进行分割
形成一个完整的分割结果之后，需要搜索下一个完整的分割结果，所以需要一步一步回溯，此时保存分割结果的path就需要一步一步的删除元素
执行流程
- 回溯法分割字符串，当前子串是回文串才对后面的字符串进行分割
- 将当前分割结果加入path
- 对剩下的字符串进行分割
- 形成完整的分割结果返回时，path需要删除元素
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
//存储每个分割的回文串结果
vector<vector<string>> res;
vector<string> path;
vector<vector<string>> partition(string s) {
if(s.size()==0)
return res;
backtrack(s,0,s.size());
return res;
}
//判断一个字符串是不是回文串
bool isPalindrome(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;
}
void backtrack(string s,int index,int n){
if(index==n){
res.push_back(path);
return;
}
//开始分割字符串
for(int i=index;i<n;++i){
//当前子串是回文串，后面剩下的才需要分割，否则当前子串还需要继续增加
if(isPalindrome(s,index,i)){
path.push_back(s.substr(index,i-index+1));
backtrack(s,i+1,n);
//当前分割方法统计完成需要回溯
path.pop_back();
}
//不是回文串，继续向后尝试分割，当前子串不需要分割
}
}
}
|
总结
主要是形成一个回文串，才可以对剩余的字符串进行分割，所以分割和回溯的逻辑都写在了if语句里面，形成一个完整的分割结果时，将分割结果存储到res中