Chương trình kiểm tra số ký tự tối thiểu cần chèn để chuỗi thành palindrome bằng Python

Cho chuỗi s, tìm số ký tự tối thiểu cần chèn để chuỗi trở thành palindrome.

Ví dụ: s = "mad" → 2 (chèn "am" thành "madam").

Quy trình giải quyết (Đệ quy + Memoization)

1. Định nghĩa hàm dp(i, j): số ký tự cần chèn cho chuỗi con s[i..j].
2. Nếu i >= j, trả về 0.
3. Nếu s[i] == s[j], trả về dp(i+1, j-1).
4. Ngược lại, trả về min(dp(i+1, j), dp(i, j-1)) + 1.
5. Gọi dp(0, len(s)-1).

Ví dụ mã nguồn

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

Đầu vào

s = "mad"

Đầu ra

2