38分割回文串（131）

作者: Turbo时间限制: 1S章节: 深度优先搜索

晚于: 2020-07-29 12:00:00后提交分数乘系数50%

截止日期: 2020-08-05 12:00:00

问题描述 :

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案的数量。

示例:

输入: "aab"

输出: 2

说明：可能的分割方案有：

[

  ["aa","b"],

  ["a","a","b"]

]

输入说明 :

输入一个字符串 s，长度小于等于200.

输出说明 :

输出一个整数

输入范例 :

aab

输出范例 :

2

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> res;
    void backtrack(string s,vector<string>&temp,int pre)
    {
        string str;
        if(pre==s.size())//递归结束条件 
        {
            res.push_back(temp);
            return ;
        }
        for(int i=pre;i<s.size();i++)
        {
            int flag=0;
            str=s.substr(pre,i-pre+1);//分割字符串 
            int len=str.size();
            for(int j=0;j<len;j++)//先判断分割的是否是回文字符串 
            {
                if(str[j]!=str[len-1-j])
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                continue;
            temp.push_back(str);
            backtrack(s,temp,i+1);//向下递归 
            temp.pop_back();//回溯 
        }
    }
    vector<vector<string>> partition(string &s) 
    {
        int s_size=s.size();
        if(s_size==0)
            return res;
        vector<string> temp;
        backtrack(s,temp,0);
        return res;
    }
};

int main()
{
    string s;
    cin>>s;
    vector<vector<string> > res=Solution().partition(s);
    cout<<res.size()<<endl;
    return 0;
}