# 131.Palindrome Partitioning

`输入: "aab"输出:[  ["aa","b"],  ["a","a","b"]]`

`class Solution {public:    vector<vector<string>> partition(string s) {        int n=s.length(),cnt=0;        vector<vector<string>> res;        vector<string> ret;        if (n == 1)        {            ret.push_back(s);            res.push_back(ret);            return res;        }​        vector<vector<string>> tmp;        for(int i=1;i<n;i++)        {            string fir=s.substr(0,i);            if(ispalind(fir))            {                tmp=merge(fir,partition(s.substr(i,n-i)));                res.insert(res.end(),tmp.begin(),tmp.end());            }        }        if(ispalind(s))        {            ret.push_back(s);            res.push_back(ret);        }        return res;​    }    vector<vector<string>> merge(string a, vector<vector<string>>b)    {        vector<vector<string>> res;​        for(int i=0;i<b.size();i++)        {            vector<string>tmp;            tmp.push_back(a);            tmp.insert(tmp.end(),b[i].begin(),b[i].end());            res.push_back(tmp);        }        return res;    }    bool ispalind(string s)    {        int n=s.length();        for(int i=0;i<n/2;i++)            if(s[i]!=s[n-i-1]) return false;        return true;    }};`

`class Solution {    vector<vector<string>> res;​    void DFS(string& s, int begin, vector<string>& t){        if(begin>=s.length())            res.push_back(t);        else{            t.push_back("");            for(int end=begin;end<s.length();end++)                if(isParl(s, begin, end)){                    t[t.size()-1] = s.substr(begin, end-begin+1);                    DFS(s, end+1, t);                }            t.pop_back();        }    }​​    bool isParl(string& s, int begin, int end){// 可以用DP存储加速        while(begin<end){            if(s[begin]!=s[end])                return false;            begin++;            end--;        }        return true;    }public:    vector<vector<string>> partition(string s) {        vector<string> t;        DFS(s, 0, t);        return res;    }};`