# 1216. Valid Palindrome III
###### tags: `Leetcode` `Hard` `Dynamic Programming` `LCS`
Link: https://leetcode.com/problems/valid-palindrome-iii/
## 思路
如果两个字串是对方的逆序 他们俩又相等 说明这个字串是palindrome
所以本题相当于是找s和s reverse的lcs
相当于找s和s.reverse()的LCS长度 看是不是小于等于k
## Code

class Solution {
    public boolean isValidPalindrome(String s, int k) {
        StringBuilder t = new StringBuilder(s);
        t = t.reverse();
        int n = s.length();
        int[][] dp = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(s.charAt(i-1)==t.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 (n-dp[n][n])<=k;
    }
}