Chương trình kiểm tra xem liệu palindrome có thể được hình thành sau khi xóa tối đa k ký tự hay không trong python

Giả sử chúng ta có một chuỗi s, chúng ta phải kiểm tra xem chúng ta có thể biến chuỗi này thành palindrome sau khi xóa tối đa k ký tự hay không.

Vì vậy, nếu đầu vào là s =​​"lieuvrel", k =4, thì đầu ra sẽ là True, chúng ta có thể xóa ba ký tự để có được "mức" palindrome.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm lcs (). Điều này sẽ mất a, b
• m:=kích thước của a, n:=kích thước của b
• table:=ma trận có kích thước (m + 1) x (n + 1) và điền bằng 0
• đối với tôi trong phạm vi từ 1 đến m, hãy thực hiện
  • đối với j trong phạm vi từ 1 đến n, thực hiện
    • nếu a [i - 1] giống với b [j - 1], thì
      • table [i, j]:=1 + table [i - 1, j - 1]
    • nếu không,
      • table [i, j]:=tối đa của table [i, j - 1] và table [i - 1, j]
• trả về bảng [m, n]
• Từ phương thức chính, hãy làm như sau:
• trả về true khi (kích thước của s - lcs (s, đảo ngược của s) <=k) nếu không thì false

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

"lieuvrel", 4

Đầu ra

True