一个string对象，将其进行划分成若干子字符串，要求每一字符串都是回文的（即正着读和倒着读是一样的）。设计一个算法，返回所有可能的字符串。
初步分析这个问题，要对每一个自字符串再次划分，所以非常适合递归。个人感觉这个题目不太适合动态规划，因为如果把字符串划分，母字符串的结果不能由一个子字符型结果，比如abbacd的结果不能由abbac导出。算法如下：
class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>>result; if(s=="") return result; result=part(s); return result; } private: vector<vector<string>> part(string s) { vector<vector<string>>result; int length=s.size(); vector<string> single; for(int index=0;index<length;index++) { single.push_back(s.substr(index,1)); } result.push_back(single); for(int index=0;index<length;index++)//注意index=0；要从单个字符做起，因为单个字符也是回文的；我最开始把单个字符的情况单独列出，这样是不妥的 { if(s[index]==s[0]&&isPalindrome(s.substr(0,index+1)))//如果s[index]!=s[0],可以确定0到index的字符串不是回文的 { string lResult=s.substr(0,index+1); if(index!=length-1) { vector<vector<string>> rResult=part(s.substr(index+1,length-index)); int rLen=rResult.size(); for(int rIndex=0;rIndex<rLen;rIndex++) { vector<string> result1; result1.push_back(lResult); for(int rIndex2=0;rIndex2<rResult[rIndex].size();rIndex2++) { result1.push_back(rResult[rIndex][rIndex2]); } result.push_back(result1); } } else { vector<string> result1; result1.push_back(lResult); result.push_back(result1); } } } return result; } bool isPalindrome(string s) { for(int start=0,end=s.size()-1;start<end;start++,end--) { if(s[start]!=s[end]) { return false; } } return true; } };