【leetcode刷题笔记】Palindrome Partitioning II
2024-08-23 06:41:22
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,s.length]所需要的最少cut,则dp[i] = min(dp[i], dp[j+1]+1) (j=i,i+1,...,s.length)。
即如果s[i,j]是一个回文字符串,那么s[j+1,s.length]需要的最少cut,加上s[i,j]就可以得到一个cut。
如下图所示:
此题还有个坑是判断回文的时候,不能用单独的判断函数,而要在动态规划的过程中维护一个数组isPar[i][j]表示s[i,j]是否是字符串,因为我们只在s[i,j]是回文的时候才去看dp[j+1]并且得到一个cut,所以我们只需要在s(i) == s(j)的时候,利用isPar[i+1,j-1](或者j-i<2)做出s[i,j]是否是回文的判断。
代码如下:
public class Solution {
public int minCut(String s){
if(s == null || s.length() == 0)
return 0;
int length = s.length();
int[] dp = new int[length+1];
boolean[][] isPar = new boolean[length][length]; for(int i = length-1;i>=0;i--){
dp[i] = s.length() - i;
for(int j = i;j<s.length();j++){
//only if s[i] == s[j], s[i,j] may be a palindrome
if(s.charAt(i)==s.charAt(j)){
if(j-i<2 || isPar[i+1][j-1]){
isPar[i][j] = true;
dp[i] = Math.min(dp[i], dp[j+1]+1);
}
}
}
}
return dp[0]-1;
}
}
最新文章
- nginx配置
- Python——函数的命名关键字参数
- 查看 table,view,sp的定义
- node模块的分类
- ApacheServer-----关于443端口被占用的解决方法
- smaller programs should improve performance
- windows 80端口被占用的解决方法
- JS对文本框值的判断
- 1523. K-inversions(K逆序对)
- 1行代码为每个Controller自定义“TabBar”-b
- fopen/fclose
- Jsp内置对象-session
- Eclipse无法打开“Failed to load the JNI shared library”
- 100% width CSS 在 iPad / iPhone Safari 背景被截断 / 显示不全
- 【转载】javascript 杂谈之哪种写法你更喜欢?
- HOW TO LINK THE TRANSACTION_SOURCE_ID TO TRANSACTION_SOURCE_TYPE_ID
- ruby中如何调用与局部变量同名的私有方法
- 外网win10 64位环境下 为内网win7 32位安装三方包的最靠谱手段:python64位、32位全安装。
- Django框架的探索
- iOS学习——(转)iOS中关于通知的使用