โปรแกรมตรวจสอบจำนวนอักขระขั้นต่ำที่จำเป็นในการสร้างสตริง palindrome ใน Python

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

ดังนั้น หากอินพุตเป็น s ="mad" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถแทรก "am" เพื่อรับ "mad" ได้

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

• กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j

• ถ้า i>=j แล้ว

  • คืนค่า 0

• ถ้า s[i] เหมือนกับ s[j] แล้ว

  • ส่งคืน dp(i + 1, j - 1)

• มิฉะนั้น

  • คืนค่าต่ำสุดของ dp(i + 1, j) และ dp(i, j - 1) + 1

• จากวิธีหลัก ให้ทำดังนี้

• ส่งคืน dp(0, ขนาดของ s - 1)

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

ตัวอย่าง

class Solution:
   def solve(self, s):
      def dp(i, j):
         if i >= j:
            return 0
         if s[i] == s[j]:
            return dp(i + 1, j - 1)
         else:
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
      return dp(0, len(s) - 1)
ob = Solution()
s = "mad"
print(ob.solve(s))

อินพุต

s = "mad"

ผลลัพธ์

2