1.题目描述

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"]

  ]

也就是给定一个字符串，找出所有可能的划分，每一个划分的每一个字串都是回文串。设这个划分函数为partition_index（string s，int begin，int end）

2.解题思路

蛮力法当然是可以解决这个题目，对于一个长度为n的字符串，有2^n-1种划分办法，只须要断定每种划分是否满足前提即可，固然不知道暴力法能不克不及在体系里面ac掉，然则如许显然不是一个正常的法度员该干的事。不过蛮力给我们一些启发。我们从为什么蛮力有2^n-1种划分办法开端解析。

当然，这也很轻易解析，对于长度为n的字符串s₀s₁…s_k…s_n-1，在s_k和s_k-1之间我们可以选择截断与不截断，然则，我们可以基于这个思路理出一个递归的思路，那就是，对于字符串s_begins_begin+1…s_begin+k…s_n-1，所有可能满足前提的划分分为两类：

（1）在s_begin和s_begin+1之间有隔断间隔，这种景象，只需s_begin和partition_index（s，begin+1，n-1）连接起来即可

（2）在s_begin和s_begin+1之间无隔断间隔，这种景象，需找到至少包含s_begin和s_begin+1的一个回文字符串，若是可以或许找到，比如，s_begin…s_begin+k是一个回文字符串，那么，将这个回文字符串和partition_index（s，k+1，n-1）连接起来，重视，可能找到不止一个包含s₀和s₁的回文字符串，那么有几许个，就多出几许类划分可能；若是找不到，那么返回空vector.

3.代码

＃include <iostream> ＃include <vector> ＃include <string> ＃include <iterator> using namespace std; vector<vector<string> > partition（string s）; vector<vector<string> > partition_index（string s， int begin， int end）; bool isPalindrome（string s， int begin，int end）; int main（） { partition（"cdd"）; return 0; } &＃160; vector<vector<string> > partition（string s） { &＃160; return partition_index（s，0，s.length（）-1）; } &＃160; vector<vector<string> > partition_index（string s， int begin， int end） { vector<vector<string> > result; &＃160; //鸿沟前提 if（begin == end） { vector<string> item; item.push_back（s.substr（begin，1））; result.push_back（item）; return result; } if（begin > end） return result; //若是在begin与begin+1之间有划分 vector<vector<string> > result_part1; result_part1 = partition_index（s，begin+1，end）; if（!result_part1.empty（）） { vector<vector<string> >::iterator iter_vv; for（iter_vv = result_part1.begin（）;iter_vv!=result_part1.end（）;++iter_vv） { vector<string> temp; //temp = iter_vv; temp.push_back（s.substr（begin，1））; vector<string>::iterator iter_v; for（iter_v = （iter_vv）.begin（）;iter_v!= （iter_vv）.end（）;++iter_v） { temp.push_back（iter_v）; } result.push_back（temp）; } } //若是在begin和begin+1之间无划分 int nextSeg = begin +1; while（nextSeg<=end） { &＃160; //找到了回文字符串 if（isPalindrome（s，begin，nextSeg）） { vector<vector<string> >result_part2_1; result_part2_1 = partition_index（s，nextSeg+1，end）; if（!result_part2_1.empty（）） { vector<vector<string> >::iterator iter_vv; for（iter_vv = result_part2_1.begin（）;iter_vv!=result_part2_1.end（）;++iter_vv） { vector<string> temp; // temp = iter_vv; temp.push_back（s.substr（begin，nextSeg））; vector<string>::iterator iter_v; for（iter_v = （iter_vv）.begin（）;iter_v!= （iter_vv）.end（）;++iter_v） { temp.push_back（iter_v）; } result.push_back（temp）; } } else { vector<string>temp; temp.push_back（s.substr（begin，nextSeg-begin+2））; result.push_back（temp）; } } //持续找看是否有其他的更长的回文字符串 nextSeg++; } return result; } &＃160; &＃160; //断定字符串由begin 和end 断定的字串是否为回文字符串 bool isPalindrome（string s， int begin，int end） { if（begin>end）return false; if（begin==end）return true; if（（begin+1）==end）return s[begin]==s[end]; else if（s[begin]==s[end]） return isPalindrome（s，begin+1，end-1）; esle return false; } &＃160; 真正的心灵世界会告诉你根本看不见的东西，这东西需要你付出思想和灵魂的劳动去获取，然后它会照亮你的生命，永远照亮你的生命。——王安忆《小说家的十三堂课》 分享到： 相关文章 python开辟_python中的range（）函数 基于最小错误率的贝叶斯决定计划 java 版本SQLHelper string，CString，char*之间的转化 采集会提高网站的收录吗 struts1与strut2的差别 vs2010里面的ipch文件和.sdf文件是什么 关于No ManagedConnections available within configure POJ 1226 Substrings 解题呈报 由Java中toString（）办法激发的无意识的递归想到的 咨询 咨询 售后 售后 浙ICP备08005872号 版权所有 杭州辉煌软件有限公司 copyright 2004 All Rights Reserved 联系电话：0571-83865188　　　本部地址：浙江杭州萧山区新塘街道