分割回文串

分割回文串

思路：分成两部，第一步，把所有分割的字串表示出来，

第二步,写一个函数判断是否是回文串即可。

判断是否是回文串也可以用动态规划预处理。

class Solution {bool if_hwc(string s,int a,int b)//a为起始位置，b为终止位置 判断是否为回文串{for(int i=a,j=b;i<j;i++,j--){if(s[i]!=s[j]) return false;}return true;}void hwc(vector<vector<string>> &ans,vector<string>&path,int currentstep,string &s){if(currentstep==s.size()){ans.push_back(path);return;}for(int i=currentstep;i<s.size();i++){if(if_hwc(s,currentstep,i)){path.push_back(s.substr(currentstep,i-currentstep+1));hwc(ans,path,i+1,s);path.pop_back();}}}
public:vector<vector<string>> partition(string s) {vector<vector<string>> ans;vector<string>path;hwc(ans,path,0,s);return ans;}
};