给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
https://leetcode-cn.com/explore/interview/card/top-interview-quesitons-in-2018/275/string/1137/
方案数可以用dp，方案就只会暴力了。
ac代码：
class Solution {
public:
vector <string> part;
vector<vector<string>> ans;
int n,root = 0;
bool check(int L,int R,string s){
for(int i = 0 ; i <= (R-L+1)/2 ; i++){
if(s[L+i] != s[R-i]) return false;
}
return true;
}
void dfs(int pos,string s){
if(pos >= n){
ans.push_back(part);
return ;
}
for(int i = pos ; i < n ; i++){
if(!check(pos,i,s)) continue;
part.push_back(s.substr(pos,i-pos+1) );
dfs(i+1,s);
part.pop_back();
}
}
vector<vector<string>> partition(string s) {
n = s.length();
for(int i = 0 ; i < n ; i++){
if(!check(0,i,s)) continue;
part.clear();
part.push_back(s.substr(0,i+1));
dfs(i+1,s);
}
return ans;
}
};
全部代码：
#include <bits/stdc++.h>
using namespace std;
string s;
vector <vector <string> >ans;
vector <string> part;
const int maxn = 1e5+10;
int n,root = 0;
bool check(int L,int R){
for(int i = 0 ; i <= (R-L+1)/2 ; i++){
if(s[L+i] != s[R-i]) return false;
}
return true;
}
void dfs(int pos){
if(pos >= n){
ans.push_back(part);
return ;
}
for(int i = pos ; i < n ; i++){
if(!check(pos,i)) continue;
part.push_back(s.substr(pos,i-pos+1) );
dfs(i+1);
part.pop_back();
}
}
void sov(){
n = s.length();
for(int i = 0 ; i < n ; i++){
if(!check(0,i)) continue;
part.clear();
part.push_back(s.substr(0,i+1));
dfs(i+1);
}
}
int main(){
cin>>s;
sov();
}
