โปรแกรมตรวจสอบว่า palindrome สามารถสร้างขึ้นหลังจากลบอักขระไม่เกิน k ตัวหรือไม่ใน python

สมมติว่าเรามีสตริง s เราต้องตรวจสอบว่าเราสามารถทำให้สตริงนี้เป็นพาลินโดรมหลังจากลบอักขระได้ไม่เกิน k ตัวหรือไม่

ดังนั้น หากอินพุตเป็น s ="lieuvrel", k =4 เอาต์พุตจะเป็น True เราสามารถลบอักขระสามตัวเพื่อรับ "ระดับ" ของ palindrome

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน lcs() นี่จะใช้เวลา a, b
• m :=ขนาดของ a, n :=ขนาดของ b
• ตาราง :=เมทริกซ์ขนาด (m + 1) x (n + 1) และเติมด้วย 0
• สำหรับฉันในช่วง 1 ถึง m ทำ
  • สำหรับ j ในช่วง 1 ถึง n ทำ
    • ถ้า a[i - 1] เหมือนกับ b[j - 1] แล้ว
      • ตาราง[i, j] :=1 + ตาราง[i - 1, j - 1]
    • มิฉะนั้น
      • table[i, j] :=สูงสุดของ table[i, j - 1] และ table[i - 1, j]
• กลับตาราง[m, n]
• จากวิธีหลัก ให้ทำดังนี้:
• คืนค่า จริง เมื่อ (ขนาดของ s - lcs(s, ย้อนกลับของ s) <=k) มิฉะนั้น จะเป็นเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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