leecode 解题总结：131. Palindrome Partitioning

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:Given a string s, partition s such that every substring of the partition is a palindrome.Return all possible palindrome partitioning of s.For example, given s = "aab",Return[  ["aa","b"],  ["a","a","b"]]分析:此题给定一个字符串，对该字符串进行划分，使得划分后的每个字符串都是一个回文字符串。返回所有可能的划分。首先明确将字符串划分成每个子串的长度为1的时候，必定是一个回文字符串。当长度不为1，需要需要判断当前划分的字符串是否已经是回文的，如果是回文的，将该划分存入结果集；然后对该字符串再次划分，直到各个子串的长度都为1。但是这样有一个问题就是:如果aabb是回文的，将aabb压入结果集将aabb划分为"" , aabb，发现是压入结果，需要后续处理,结果空字符串不处理，又处理aabb，然后会陷入死循环            a, abb 不是，不进行后续划分处理			aa,bb,发现是，压入结果集，并对aa,和bb进行分解，发现aa也是，划分得到: a, a 存入结果集，但是需要和bb划分后的结果集一起存入bb, b,b做笛卡尔积			      对aa处理,划分为: a a,aa 返回				  对bb处理，划分为: b b,bb 返回				  <{a a, aa}>和<{b b,bb}>进行笛卡尔积，得到四种			aab,b，不是，不作处理			aabb,"",发现是，这种情况单独直接压入，然后不做后续递归处理，如果处理会变成死循环aab:      a ,  ab	 aa, b	 aa,b	 aab,"" 这个和"" ,aab是一样的	 最后一次划分会重复	 这个递归会有问题:	 aab: a ab-> a ab:{a} {a b} ,得到 {a a b}	      aa b-> {aa},{b}: {aa,a a},{b}得到{aa b, a a b},出现重复		  aab 0->重复，无需递归，直接返回结果		  最好能保留一个计算结果：如果已经计算过，直接返回，键为: 起始位置#结束位置，值为vector< vector<string> >           输入:aababaabb输出:aa b,a a ba baabb, aa bb, a a bb, aa b b, a a b b关键：1leecode解法:https://leetcode.com/PRoblems/palindrome-partitioning/?tab=Solutions采用回溯：采用一个循环，先对S[0..i]判断是否是回文串，如果是回文串，将该回文串压入结果；并且对S[i+1...n]递归判断是否是回文串，当前S[0..i]下的递归对S[i+1..n]处理完毕之后，将原先S[0...i]从结果集中删除，形成回溯。这样通过递归当当前位置等于字符串长度时，得到一个划分结果压入结果集；*/class Solution {public:	//判断一个字符串是否是回文串	bool isPalindrome(string& s ,int beg, int end)	{		//空字符串是回文的		if(s.empty() )		{			return true;		}		if(beg < 0 || end >= s.length() || beg > end)		{			return false;		}		int low = beg;		int high = end;		bool isOk = true;		while(low < high)		{			if(s.at(low) != s.at(high))			{				isOk = false;				break;			}			low++;			high--;		}		//如果当前字符串是回文串，存入结果集		return isOk;	}	void backTrace(int begin , string& s ,vector<string>& result , vector< vector<string> >& results)	{		if(begin < 0 || s.empty())		{			return;		}		if(begin == s.length())		{			results.push_back(result);			return;		}		int len = s.length();		for(int i = begin ; i < len ;i++ )		{			//判断当前是否是回文串，如果是，才继续递归对右边部分字符串进行递归处理			if(isPalindrome(s , begin , i))			{				result.push_back( s.substr(begin , i - begin + 1 ));				backTrace(i + 1 , s , result , results);				//弹出当前回文串，供生成其他有效的回文串划分				result.pop_back();			}		}	}    vector<vector<string>> partition(string s) {		vector<vector<string> > results;		if(s.empty())		{			return results;		}		vector<string> result;		backTrace(0 , s ,result , results);		return results;    }};void print(vector<vector<string> >& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	int len;	for(int i = 0 ; i < size ; i++)	{		len = result.at(i).size();		for(int j = 0 ; j < len ; j++)		{			cout << result.at(i).at(j) << " " ;		}		cout << ", ";	}	cout << endl;}void process(){	 string value;	 Solution solution;	 vector<vector<string> > result;	 while(cin >> value )	 {		 result = solution.partition(value);		 print(result);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*	//返回当前字符串划分后的所有字符串有效组合	vector< vector<string> > dfs(string& s , int beg ,int end )	{		vector<string> result;		vector< vector<string> > results;		if(s.empty())		{			return results;		}		if( beg < 0 || end >= s.length())		{			return results;		}		//这种情况不可能，直接返回		if(beg > end)		{			return results ;		}		//如果当前只有一个字符，肯定符合是回文串，直接返回		if(beg == end)		{			result.push_back(s.substr(beg , 1));			results.push_back(result);			return results;		}		//当前本身是一个字符串，就压入到结果集,这个不需要了，可以通过后续划分来判断			//对字符串进行划分,分成(beg , i),(i, end)		int len = s.length();		bool isLeftOk;		bool isRightOk;		vector< vector<string> > totalLeft;		vector< vector<string> > totalRight;		vector< vector<string> > leftResult;		vector< vector<string> > rightResult;		vector<string> tempResult;		string sLeft;		string sRight;		int leftSize;		int rightSize;		int i;		int j;		int k;		for(i = beg ; i <= end ; i++)		{			//先直接判断这两个字符串本身是否是回文的,如果两个字符串本身不是回文的，后面不进行递归？ ab不是回文，需要拆分为a b就是回文了, abc, a bc , ab c, abc ""			//这里对两个长度为1的字符串不做处理，因为后续递归会处理			if(!(i == beg && i + 1 == end))			{				isLeftOk = isPalindrome(s , beg , i);				isRightOk = isPalindrome(s, i+1 , end);				if(isLeftOk && isRightOk)				{					sLeft = s.substr(beg ,i - beg + 1);					sRight = s.substr(i+1 , end - i);					if(!sLeft.empty())					{						vector<string> tempResult1;						tempResult1.push_back(sLeft);						totalLeft.push_back(tempResult1);					}					if(!sRight.empty())					{						vector<string> tempResult1;						tempResult1.push_back(sRight);						totalRight.push_back(tempResult1);					}				}			}			//如果i == end，则字符串又等于当前字符串了，会陷入死循环，因此，不能进行递归			if(i != end)			{				leftResult = dfs(s , beg , i );				rightResult = dfs(s ,  i + 1 , end);				//如果左右都是回文的，把左右各自划分后的结果进行笛卡尔积运算				if(!leftResult.empty())				{					leftSize = leftResult.size();					for(j = 0 ; j < leftSize ;j++)					{						totalLeft.push_back(leftResult.at(j));					}				}				if(!rightResult.empty())				{					rightSize = rightResult.size();					for(j = 0 ; j < rightSize;  j++)					{						totalRight.push_back(rightResult.at(j));					}				}			}			//进行笛卡尔积运算			if(!totalLeft.empty() && !totalRight.empty())			{				leftSize = totalLeft.size();				rightSize = totalRight.size();				for(j = 0 ; j < leftSize ;j++)				{					for(k = 0; k < rightSize; k++)					{						tempResult = totalLeft.at(j);						tempResult.insert(tempResult.end() , totalRight.at(k).begin() , totalRight.at(k).end());						results.push_back(tempResult);					}				}			}			else if(totalLeft.empty())			{				leftSize = totalLeft.size();				for(j = 0 ; j < leftSize ; j++)				{					results.push_back(totalLeft.at(j));				}			}			else if(totalRight.empty())			{				rightSize = totalRight.size();				for(j = 0 ; j < rightSize ; j++)				{					results.push_back(totalRight.at(j));				}			}		}		return results;	}*/