#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;	}*/