回溯之寻找回文子串

寻找回文子串

#include<bits/stdc++.h>
using namespace std;
class Solution{
	private:
		vector<string> path;
		vector<vector<string> >result;
	public:
		bool isRev(const string& s,int begin,int end){
			for(int i=begin,j=end;i<j;i++,j--){
				//这里利用了双指针的写法 
				if(s[i]!=s[j]){
					return false;
				}
			}
			return true;
		}
		void backTracking(const string& s,int startIndex){
			if(startIndex>=s.size()){
				result.push_back(path);
				return;
				//终止条件 
			}
			for(int i=startIndex;i<s.size();i++){
				if(isRev(s,startIndex,i)){
					string str=s.substr(startIndex,i-startIndex+1);
					//截取子串 
					path.push_back(str);
				}
				else{
					continue;
				}
				backTracking(s,i+1);
				//回溯 
				path.pop_back();
			}
		}
		vector<vector<string> > combine(string s){
			backTracking(s,0);
			return result;
		}
};
int main()
{
    Solution solution;
    vector<vector<string> > result;
    result = solution.combine("abb");
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j] << " ";
        }
        cout<<endl;
    }
    return 0;
}

欢迎批评指正！