注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex132 Palindrome Partitioning II  

2015-05-22 21:28:29|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
上一题 Palindrome Partitioning ex131的升级版。多了一层动态规划

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

就是在切割的时候加了一些限制,必须用最少的切割次数,完成分割。
还是一样的想法,先求出回文矩阵,接着根据矩阵来动态递推当前到最后切割完成需要最少的步骤,关于外层的动态规划见下图。大致思想是这样,开一dp数组,dp[i]表示从i到最后的最小步骤。我们从后往前推
假设i->j回文的话那么
dp[i] = min(dp[i],d[j+1]+1); 
意思就是说,从i->j我们一步走完,后面的步数+1更新到dp[i]中ex132 Palindrome Partitioning II - HT - HT·生活
 下面是c++代码

int myMin(int a, int b)
{
return a > b ? b : a;
}
class Solution {
public:
vector<vector<bool>> matrix;
vector<vector<string>>result;
int minCut(string s) {

matrixPalindrome(s);//首先将matrix算出来
vector<int>cut(s.size()+1,0); //全部初始化为0
//cut[i]表示,从i到string的末尾需要切割的刀数

int i, j;
int len = s.size();
for (i = len - 1; i >= 0; i--)
{
cut[i] = len - i; //开始的时候假设都是每一个字母都分割
//外循环从后往前更新
for (j = i; j < len; j++)
{
if (matrix[i][j])
{
//i->j是可以切割的,那么 cut[i] 就等于原来的和 cut[j+1]+1的较小值
cut[i] = myMin(cut[j + 1] + 1,cut[i]);
//内循环从前往后更新
}
}
}
//最后一个字符不需要切割,所以减去1

return cut[0]-1;
}
vector<vector<bool>> matrixPalindrome(string s) {

int n = s.length();
vector<vector<bool>> dp;
//为基准情况赋值
int i, j;
vector<bool> temp(n,false);
for (i = 0; i < n; i++)
{
dp.push_back(temp);
//最好不要做两个大循环容易超时
}

int startPos = 0;
int max = 1;
for (i = 0; i < n; ++i)
{
dp[i][i] = true;
if (i + 1 < n)
{
if (s[i] == s[i + 1])
{
dp[i][i + 1] = true;
startPos = i;
max = 2;
}
else dp[i][i + 1] = false;
}
}

//动规求解,前面已求len = 1, len = 2的情况
int len;
for (len = 3; len <= n; ++len)
{
for (i = 0; i < n - len + 1; ++i)
{
j = i + len - 1;

if (dp[i + 1][j - 1] && s[i] == s[j])
{
dp[i][j] = true;
int curLen = j - i + 1;
if (curLen > max)
{
startPos = i;
max = curLen;
}
}
else dp[i][j] = false;

}
}
matrix = dp;

return dp;
}
};

参考
这位作者总结了ex131和ex132,写的挺不错的。
http://blog.csdn.net/u011095253/article/details/9177451





  评论这张
 
阅读(22)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017