用于在python中删除最多k个字符后检查回文是否可以形成的程序

假设我们有一个字符串s，我们必须检查在删除最多k个字符后是否可以使该字符串成为回文。

因此，如果输入像s =“ lieuvrel”，k = 4，则输出将为True，我们可以删除三个字符以得到回文“级别”。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个功能lcs()。这需要a，b

• m：= a的大小，n：= b的大小

• 表格：=大小（m + 1）x（n + 1）的矩阵并填充0

• 对于1到m范围内的i

• 如果a [i-1]与b [j-1]相同，则

• 除此以外，

• table [i，j]：= 1 + table [i-1，j-1]

• table [i，j]：= table [i，j-1]和table [i-1，j]的最大值

• 对于1到n范围内的j，执行

• 返回表[m，n]

• 从主要方法执行以下操作：

• 当（s的大小-lcs（s，s的倒数）<= k）时返回true，否则返回false

让我们看下面的实现以更好地理解-

例 

class Solution:
   def solve(self, s, k):
      def lcs(a, b):
         m, n = len(a), len(b)
         table = [[0] * (n + 1) for _ in range(m + 1)]
         for i in range(1, m + 1):
            for j in range(1, n + 1):
               if a[i - 1] == b[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
               else:
                  table[i][j] = max(table[i][j - 1], table[i - 1][j])
         return table[m][n]

      return len(s) - lcs(s, s[::-1]) <= k
     
ob = Solution()s = "lieuvrel"
k = 4
print(ob.solve(s, k))

输入值

"lieuvrel", 4

输出结果

True