20210308 132. 分割回文串 II

题目

https://leetcode-cn.com/problems/palindrome-partitioning-ii/

题解

这个想到 https://leetcode-cn.com/problems/palindrome-partitioning/ 这个题,只要path变成integer就可以,但是这么递归会超时.

所以需要优化的地方一个是判断一个子串是否是回文串,一个是通过dp来找最小值

优化回文子串判断

设定一个boolea[][] 如果s.charAt[1]==s.charAt[j] boolean[i][j] = boolean[i+1][j-1]

dp求回文子串最小值

该字符独立消耗一次分割次数。此时有 f[j] = f[j – 1] + 1
该字符不独立消耗一次分割次数,而是与前面的某个位置 i 形成回文串,[i, j] 作为整体消耗一次分割次数。此时有 f[j] = f[i – 1] + 1

public int minCut(String s) {
char[] charArray = s.toCharArray();
boolean[][] hArray = new boolean[charArray.length][charArray.length];
for (int i = charArray.length - 1; i >= 0; i--) {
for (int j = i; j < charArray.length; j++) {
if (j - i <= 1) {
hArray[i][j] = charArray[i] == charArray[j];
} else {
hArray[i][j] = hArray[i + 1][j - 1] && charArray[i] == charArray[j];
}
}
}
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (hArray[0][i]) {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 1;
for (int j = 1; j < i; j++) {
if (hArray[j][i]) {
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
}
}
return dp[s.length() - 1];
}

发表评论

邮箱地址不会被公开。 必填项已用*标注