[Leetcode]Palindrome Partitioning II

作者:武汉味美食家餐饮管理有限公司 来源:www.cj17917.com 发布时间:2017-09-02 11:51:53
[Leetcode]Palindrome Partitioning II 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.

给定一个字符串,求最少的切割次数是的切割的结果都是回文串。

一个思路

首先想到:如果能预处理好所有的下标之间的字符串是否为回文字符串的话,在后面求最少切割次数的时候就不需要再扫描字符串来判断了。这部分代码如下:

boolean[][] isP = new boolean[s.length()][s.length()];

for (int k = 0; k < s.length(); k++) {

for (int i = 0, j = i + k; j < s.length(); i++, j++) {

if (i == j || (s.charAt(i) == s.charAt(j) && (j - i == 1 || isP[i + 1][j - 1]))) {

isP[i][j] = true;

}

}

}

下面在来看怎么求得最少的切割次数,最初的想法是用dp[i][j]表示从下标i到下标j之间能满足题目要求的切割次数。状态转移方程为:

dp[i][j] = min(dp[i][l] + dp[l+1][j])

这样总共有O(N^2)个状态,每次状态转移需要O(N),总的复杂度变为O(N^3),提交之后不出预料地超时了,需要重新思考状态的设置。

最后要求的结果是整个字符串的最小切割次数,如果结果大于0,那么必然有一刀把字符串的最后一截回文串切下来了(不然的话不满足要求啊~),那么总的切割的次数就是前面剩余的字符串的切割次数加一。考虑到最后一个字符开始的回文字符串可能很多,从中选出一个最小的就可以了。那么,ret[i]表示从0到i的最小切割次数,那么状态转移方程变成:

isP[j+1][i] = true? ret[i] = min(ret[i], ret[j] + 1)

当然还需要考虑的一个特殊情况是0到i本身就是一个回文串的话,那么显然ret[i] = 0。这部分代码如下:

int[] ret = new int[s.length()];

for (int i = 1; i < s.length(); i++) {

if (isP[0][i]) {

ret[i] = 0;

} else {

int min = 0x7fffffff;

for (int j = 1; j <= i; j++) {

if (isP[j][i] && ret[j - 1] + 1 < min) {

min = ret[j - 1] + 1;

}

}

ret[i] = min;

}

}

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉SEO http://wuhan.raoyu.net

  • 上一篇:50跨站cookie的有关问题
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 武汉味美食家餐饮管理有限公司 ALL RIGHTS RESERVED.
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100