Python 程序：检查删除最多 k 个字符后是否可以形成回文

假设我们有一个字符串 s，我们需要检查是否可以通过删除最多 k 个字符将其变成回文。

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

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

  • 定义一个函数 lcs()。它将接收 a 和 b 作为参数。
  • m := a 的大小，n := b 的大小
  • table := (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] 中的最大值
  • 返回 table[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

更新于: 2020-12-03

492 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告