Chương trình kiểm tra số ký tự tối thiểu cần thiết để tạo chuỗi palindrome trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số ký tự tối thiểu cần thiết để được thêm vào để chuỗi trở thành một palindrome.

Vì vậy, nếu đầu vào là s =​​"mad", thì đầu ra sẽ là 2, vì chúng ta có thể chèn "am" để nhận "madam".

Để 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 dp (). Điều này sẽ mất tôi, j

• nếu tôi> =j, thì

  • trả về 0

• nếu s [i] giống với s [j] thì

  • trả về dp (i + 1, j - 1)

• nếu không,

  • trả về tối thiểu dp (i + 1, j) và dp (i, j - 1) + 1

• Từ phương thức chính, thực hiện như sau

• trả về dp (0, kích thước của s - 1)

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

Đầu vào

s = "mad"

Đầu ra

2