Chương trình tìm độ dài của dãy con palindromic dài nhất trong Python

Giả sử chúng ta có một chuỗi chữ thường s; chúng ta phải tìm độ dài của dãy con palindromic dài nhất tính bằng s.

Vì vậy, nếu đầu vào là s =​​"aolpeuvekyl", thì đầu ra sẽ là 5, vì palindrome là "cấp".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s
• Định nghĩa một hàm dp (). Điều này sẽ mất tôi, j
• nếu tôi giống với j, thì
  • trả lại 1
• ngược lại khi i> j, thì
  • trả về 0
• nếu không,
  • nếu s [i] giống với s [j], thì
    • return 2 + dp (i + 1, j - 1)
  • nếu không,
    • trả về tối đa dp (i + 1, j) và dp (i, j - 1)
• trả về dp (0, n - 1)

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

"aolpeuvekyl"

Đầu ra

5