05 August 2008
移除k次字符后，是否能成为回文字符串
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public boolean isValidPalindrome(String s, int k) {
int rows = s.length(), cols = s.length();
int[][] dp = new int[rows][cols];
for (int i = 1; i < rows; i++) {
if (s.charAt(i - 1) == s.charAt(i)) {
dp[i - 1][i] = 0;
} else {
dp[i - 1][i] = 1;
}
}
for (int x = 2; x < rows; x++) {
int i = 0, j = x;
while (j < cols) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
}
i++;
j++;
}
}
return dp[0][cols - 1] <= k;
}
}