132. 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.
Example:
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
本题可以看成一个动态规划题目。有以下两点可作为递推条件(cut[i]表示s.subString(0, i+1)满足题意的分割次数):
1,cut\[i\]的值为当0 <= j <= i时,cut\[j\]的最小值加1。
2,如果s.subString(j, i+1)是回文字符串且s.charAt(j-1)==s.charAt(i+1),则s.subString(j-1, i+2)也是回文字符串。
public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];//cut[i]表示s.subString[i]达到题目要求的最小分割次数
boolean[][] isPalinized = new boolean[n][n];//isPalinized[i][j]判断c[i]...c[j]组成的字符串是否是回文字符串
for(int i = 0; i < n; ++i) {
int min = i;//min等会赋值给cut[i],此时最大分割次数为i次
for(int j = 0; j <= i; ++j) {
if(c[j] == c[i] && (j + 1 > i - 1/**表示j + 1 == i这种情况**/ || isPalinized[j+1][i-1])) {
isPalinized[j][i] = true;
min = j == 0 ? 0/**表示s.subString(0, i+1)是回文的,即0次分割就能达到题目要求**/ : Math.min(min, cut[j-1] + 1/**s.subString(0, i+1)中,s.subString(j, i+1)是回文字符串所以此次结果为cut[j-1]+1**/)/**如上所说,min要赋值给cut[i],所以对所有情况,更新min**/;
}
}
cut[i] = min;
}
return cut[n-1];
}
还没有评论,来说两句吧...