leetcode分割回文串

给定一个字符串 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();
}