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 kcharacters 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

(Dynamic Programming): https://www.acwing.com/solution/LeetCode/content/5099/

This question is the same as asking how many characters should be deleted to make it a palindrome. f(i,j)Representing the interval [i, j]becomes a palindrome string minimum number of characters to be deleted.

Initially,f( i , i ) = 0f(i,i)=0,f( i , i − 1 ) = 0f(i,i−1)=0And the rest are positive infinity.

in case s [ i ] = = s [ j]s[i]==s[j],then f( i , j) = f( i + 1 , j− 1 )f(i,j)=f(i+1,j−1);otherwise,f( i , j) = min ( f( i + 1 , j) + 1 , f( i , j− 1 ) + 1 )f(i,j)=min(f(i+1,j)+1,f(i,j−1)+1). Here you need to enumerate by interval length.

The final answer is f( 0 , n − 1 ) ≤ kf(0,n−1)≤k.

class Solution {

public:

    bool isValidPalindrome(string s, int k) {

        int n = s.length();

        vector<vector<int>> f(n, vector<int>(n, n));

        for (int i = 0; i < n; i++)

            f[i][i] = 0;

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

            f[i][i - 1] = 0;

        for (int len = 2; len <= n; len++)

            for (int i = 0; i < n - len + 1; i++) {

                int j = i + len - 1;

                if (s[i] == s[j])

                    f[i][j] = f[i + 1][j - 1];

                else

                    f[i][j] = min(f[i][j - 1] + 1, f[i + 1][j] + 1);

            }

        return f[0][n - 1] <= k;

    }

};

作者：wzc1995

链接：https://www.acwing.com/solution/LeetCode/content/5099/

来源：AcWing

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。