本文共 819 字，大约阅读时间需要 2 分钟。

给出一个字符串 s 和一个整数 k，请你帮忙判断这个字符串是不是一个「K 回文」。

所谓「K 回文」：如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「K 回文」。

示例：

输入：s = "abcdeca", k = 2输出：true解释：删除字符 “b” 和 “e”。

提示：

• 1 <= s.length <= 1000
• s 中只含有小写英文字母
• 1 <= k <= s.length

解题思路

这实际上是lcs问题的变种，首先需要了解一下lcs问题。

我们知道回文串是对称的，也就是说我们可以通过字符串s和其反转字符串rs求最长公共子序列，其结果就是可以得到的最长回文串。

class Solution:    def isValidPalindrome(self, s: str, k: int) -> bool:        n = len(s)        def lcs(x, y):            l = [[0]*(n + 1) for _ in range(n + 1)]            for i in range(1, n + 1):                for j in range(1, n + 1):                    if x[i-1] == y[j-1]:                        l[i][j] = l[i-1][j-1] + 1                    else:                        l[i][j] = max(l[i-1][j], l[i][j-1])            return l[-1][-1]        return n - lcs(s, s[::-1]) <= k

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/102319765 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！