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

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

ตัวอย่าง: s = "mad" ผลลัพธ์ 2 (แทรก "am" ได้ "madam")

ขั้นตอนการแก้ปัญหา (DP เรียกซ้ำ / Recursion with Memoization)

1. ฟังก์ชัน dp(i, j):
   • ถ้า i >= j: คืนค่า 0
   • ถ้า s[i] == s[j]: คืนค่า dp(i+1, j-1)
   • อื่นๆ: คืนค่า min(dp(i+1, j), dp(i, j-1)) + 1
2. จากเมธอดหลัก เรียก dp(0, len(s)-1)

ตัวอย่างโค้ด Python

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))  # Output: 2

อินพุต / เอาต์พุต

Input: s = "mad"

Output: 2