leetcode—Palindrome 解题呈报
添加时间:2013-8-2 点击量:
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的字符串,有2n-1种划分办法,只须要断定每种划分是否满足前提即可,固然不知道暴力法能不克不及在体系里面ac掉,然则如许显然不是一个正常的法度员该干的事。不过蛮力给我们一些启发。我们从为什么蛮力有2n-1种划分办法开端解析。
当然,这也很轻易解析,对于长度为n的字符串s0s1…sk…sn-1,在sk和sk-1之间我们可以选择截断与不截断,然则,我们可以基于这个思路理出一个递归的思路,那就是,对于字符串sbeginsbegin+1…sbegin+k…sn-1,所有可能满足前提的划分分为两类:
(1)在sbegin和sbegin+1之间有隔断间隔,这种景象,只需sbegin和partition_index(s,begin+1,n-1)连接起来即可
(2)在sbegin和sbegin+1之间无隔断间隔,这种景象,需找到至少包含sbegin和sbegin+1的一个回文字符串,若是可以或许找到,比如,sbegin…sbegin+k是一个回文字符串,那么,将这个回文字符串和partition_index(s,k+1,n-1)连接起来,重视,可能找到不止一个包含s0和s1的回文字符串,那么有几许个,就多出几许类划分可能;若是找不到,那么返回空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;
真正的心灵世界会告诉你根本看不见的东西,这东西需要你付出思想和灵魂的劳动去获取,然后它会照亮你的生命,永远照亮你的生命。——王安忆《小说家的十三堂课》
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的字符串,有2n-1种划分办法,只须要断定每种划分是否满足前提即可,固然不知道暴力法能不克不及在体系里面ac掉,然则如许显然不是一个正常的法度员该干的事。不过蛮力给我们一些启发。我们从为什么蛮力有2n-1种划分办法开端解析。
当然,这也很轻易解析,对于长度为n的字符串s0s1…sk…sn-1,在sk和sk-1之间我们可以选择截断与不截断,然则,我们可以基于这个思路理出一个递归的思路,那就是,对于字符串sbeginsbegin+1…sbegin+k…sn-1,所有可能满足前提的划分分为两类:
(1)在sbegin和sbegin+1之间有隔断间隔,这种景象,只需sbegin和partition_index(s,begin+1,n-1)连接起来即可
(2)在sbegin和sbegin+1之间无隔断间隔,这种景象,需找到至少包含sbegin和sbegin+1的一个回文字符串,若是可以或许找到,比如,sbegin…sbegin+k是一个回文字符串,那么,将这个回文字符串和partition_index(s,k+1,n-1)连接起来,重视,可能找到不止一个包含s0和s1的回文字符串,那么有几许个,就多出几许类划分可能;若是找不到,那么返回空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;
真正的心灵世界会告诉你根本看不见的东西,这东西需要你付出思想和灵魂的劳动去获取,然后它会照亮你的生命,永远照亮你的生命。——王安忆《小说家的十三堂课》