LeetCode 1216. Valid Palindrome III

原题链接在这里：https://leetcode.com/problems/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
s has only lowercase English letters.
1 <= k <= s.length

题解：

Find the longest palindrome from s.

And check the difference between s and longest palindrome length, if it is <= k, then return true.

Time Complexity: O(n^2). n = s.length().

Space: O(n^2).

AC Java:

 class Solution {

     public boolean isValidPalindrome(String s, int k) {

         if(s == null || s.length() <= k){

             return true;

         }

         int lp = findLongestPalin(s);

         return s.length() - lp <= k;

     }

     private int findLongestPalin(String s){

         if(s == null || s.length() == 0){

             return 0;

         }

         int n = s.length();

         int [][] dp = new int[n][n];

         for(int i = n-1; i>=0; i--){

             dp[i][i] = 1;

             for(int j = i+1; j<n; j++){

                 if(s.charAt(i) == s.charAt(j)){

                     dp[i][j] = dp[i+1][j-1] + 2;

                 }else{

                     dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);

                 }

             }

         }

         return dp[0][n-1];

     }

 }

类似Longest Palindromic Subsequence, Valid Palindrome, Valid Palindrome II.

巴特西

LeetCode 1216. Valid Palindrome III

最新文章

热门文章