分割回文串
class Solution { public: vector<vector<string>> result; //判断字串是否是回文串 bool check(const string &s) { for(int i=0 ; i<s.size()/2 ; i++) { if(s[i] != s[s.size()- 1 -i]) return false; } return true; } void backtracking(string s , int indnx ,vector<string> &path) { //当循环指针大于等于最大值的时候，认为分割出一种结果 if(indnx >= s.size()) { result.push_back(path); return; } //循环字符串长度，从index当前的运行指针开始切割回文串 for(int i = indnx ; i<s.size() ;i++ ) { string tmp; //切割字串，字串是indnx到i之间。 for(int j = indnx ; j <= i ;j++) { tmp += s[j]; } // cout<<tmp<<endl; //检验字串是否为回文串，是回文串压入路径，不是i+1，进行下一个长度加1的字串 if(check(tmp)==1) path.push_back(tmp); else continue; //如果当前字串是回文串，递归indnx加1 backtracking(s,i+1,path); //回溯，弹出上一个字串 path.pop_back(); } return; } vector<vector<string>> partition(string s) { if(s.size()==0) return result; vector<string> path; backtracking(s,0,path); return result; } };
二刷
class Solution { public: vector<vector<string>> result; vector<string> path; bool cheak(string &s ,int start ,int end) { for(int i=start , j=end ; i<j ; i++,j--) { if(s[i] != s[j]) return false; } return true; } void track_back(string &s,int indnx) { if(indnx >= s.size()) { result.push_back(path); return; } for(int i=indnx ; i<s.size() ;i++) { if(cheak(s,indnx,i) == true) { string tmp = s.substr(indnx,i-indnx+1); // cout<<tmp<<endl; path.push_back(tmp); } else continue; track_back(s,i+1); path.pop_back(); } return; } vector<vector<string>> partition(string s) { track_back(s,0); return result; } };
