【Leetcode】1216. Valid Palindrome III

题目地址：

https://leetcode.com/problems/valid-palindrome-iii/description/

给定一个长$n$字符串$s$，再给定一个正整数$k$，问进行最多$k$次删除可否使得$s$变为回文串。

区间动态规划问题。设$f[l][r]$是$s[l:r]$至少经过多少次删除能成为回文串。当$l=r$的时候显然$f[l][r]=0$；当$l+1=r$的时候，如果$s[l]=s[r]$则$f[l][r]=1$，否则为$0$；其余情况，如果$s[l]=s[r]$，那么两端的字符是不需要删的，所以$f[l][r]=f[l+1][r-1]$；否则，两者必然要删一个，所以 f [ l ] [ r ] = 1 + min ⁡ { f [ l + 1 ] [ r ] , f [ l ] [ r − 1 ] } f[l][r]=1+\min\{f[l+1][r],f[l][r-1]\} f[l][r]=1+min{f[l+1][r],f[l][r−1]}。代码如下：

class Solution {
 public:
  bool isValidPalindrome(string s, int k) {
    int n = s.size();
    int f[n][n];
    memset(f, 0, sizeof f);
    for (int len = 2; len <= n; len++)
      for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        if (len == 2) f[l][r] = s[l] != s[r];
        else {
          if (s[l] == s[r]) f[l][r] = f[l + 1][r - 1];
          else f[l][r] = 1 + min(f[l + 1][r], f[l][r - 1]);
        }
      }

    return f[0][n - 1] <= k;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时空复杂度$O(n^2)$。