在Python中编写一个检查是否可以在删除最多k个字符后形成回文的程序

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

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

要解决这个问题，我们将遵循以下步骤 –

定义一个名为lcs()的函数。这将获取a，b
m：a的大小，n：b的大小
表：大小为（m+1）x（n+1）的矩阵，并填充为0
对于i在1到m的范围内，执行以下操作：
- 对于j在1到n的范围内，执行以下操作：
  - 如果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]的最大值
返回表[m，n]
从主方法中进行以下操作：
当（s的大小-lcs（s，s的反转）<= k）时，返回true，否则返回false

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

更多Python相关文章，请阅读：Python 教程

实例

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））