leetcode 1216

问题

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:

1
2
3
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

分析

思路1: 使用动态规划，$dp[i][j]$ 表示字符串 s[i...j] 转化为回文最小需要删除多少个字符。则最终答案，return dp[0][n-1] <= k 。

思路2: 求 s 的最长回文子序列，然后 s 的长度减去其最长回文子序列的长度，如果小于等于 k 则结果为 true ，否则结果为 false 。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 思路1，自顶向下
class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        return dfs(dp, s, 0, n-1) <= k;
    }
    int dfs(vector<vector<int>> &dp, const string &s, int i, int j) {
        if (i >= j) return 0;
        if (dp[i][j] >= 0) return dp[i][j];
        return dp[i][j] = s[i]==s[j]? dfs(dp, s, i+1, j-1):
            1+min(dfs(dp, s, i+1, j), dfs(dp, s, i, j-1));
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 思路1，自底向上
class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n-1; i >= 0; --i) {
            for (int j = i+1; j < n; ++j) {
                if (j == i+1) {
                    dp[i][j] = s[i]==s[j]? 0: 1;
                } else {
                    dp[i][j] = s[i]==s[j]? dp[i+1][j-1]:
                        1+min(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1] <= k;
    }
};