给一个非空的string，判断能不能只删掉一个字符变成palindrome?
例1：
Input: “aba”
Output: True
例2:
Input: “abca”
Output: True
foflow-up:如果删掉k个字符呢？
原题 https://leetcode.com/problems/valid-palindrome-ii/
public boolean validPalindrome(String s) {
int l = -1, r = s.length();
while (++l < --r)
if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);
return true;
}
public boolean isPalindromic(String s, int l, int r) {
while (++l < --r)
if (s.charAt(l) != s.charAt(r)) return false;
return true;
}
follow up是 https://leetcode.com/problems/valid-palindrome-iii/
- Valid Palindrome III
Given a string s and an integer k , find out if the given string is a K-Palindrome or not.
A string is K-Palindrome if it can be transformed into a palindrome by removing at most k characters from it.
Example 1:
Input: s = “abcdeca”, k = 2 Output: true
Explanation: Remove ‘b’ and ‘e’ characters.
Constraints:
1 <= s.length <= 1000-
shas only lowercase English letters. 1 <= k <= s.length
No.1 voted discussion
The idea is to find the longest palindromic subsequence(lps) of the given string.
|lps - original string| <= k,
then the string is k-palindrome.
Eg:
One of the lps of string pqrstrp is prsrp.
Characters not contributing to lps of the
string should be removed in order to make the string palindrome . So on removing q and s (or t) from pqrstrp, string will transform into a palindrome.
public boolean isValidPalindrome(String str, int k) {
int n = str.length();
StringBuilder stringBuilder = new StringBuilder(str).reverse();
int lps = lcs(str, stringBuilder.toString(), n, n);
return (n - lps <= k);
}
/*
longest palindromic subsequence:
LCS of the given string & its reverse will be the longest palindromic sequence.
*/
private int lcs(String X, String Y, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}