题目描述
给出一个字符串 s
和一个整数 k
,请你帮忙判断这个字符串是不是一个 K 回文。
如果可以通过从字符串中删去最多 k
个字符将其转换为回文,该字符串是一个 K 回文,
样例
输入:s = "abcdeca", k = 2
输出:true
解释:删除字符 “b” 和 “e”。
限制
1 <= s.length <= 1000
s
中只含有小写英文字母1 <= k <= s.length
算法
(动态规划) $O(n^2)$
- 此题和问最少删除多少字符可以变成回文串一样。设 $f(i, j)$ 表示区间
[i, j]
变为回文串最少需要删除多少字符。 - 初始时,$f(i, i) = 0$,$f(i, i - 1) = 0$,其余为正无穷。
- 如果 $s[i] == s[j]$,则 $f(i, j) = f(i + 1, j - 1)$;否则,$f(i, j) = \min(f(i + 1, j) + 1, f(i, j - 1) + 1)$。这里需要按照区间长度枚举。
- 最终答案为 $f(0, n - 1) \le k$。
时间复杂度
- 状态数为 $O(n^2)$,每次转移时间为常数,故时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n^2)$ 的空间记录状态。
C++ 代码
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;
}
};