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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告