โปรแกรมหาความยาวของลำดับย่อยพาลินโดรมที่ยาวที่สุดโดยใช้ Python

สมมติว่าเราได้รับสตริง เราต้องหาลำดับย่อยของพาลินโดรมที่มีความยาวเท่ากันและไม่มีอักขระสองตัวที่ต่อเนื่องกันยกเว้นตรงกลาง เราต้องคืนค่าความยาวของสตริงย่อยประเภทนี้เป็นเอาต์พุต

ดังนั้น หากอินพุตเป็น s ='efeffe' ผลลัพธ์จะเป็น 4

ผลลัพธ์คือ 4 เนื่องจากมีลำดับย่อยพาลินโดรมเพียงรายการเดียวที่มีความยาวเท่ากัน สตริงคือ 'effe' ที่มีความยาว 4

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

n :=ขนาดของ s
dp :=หนึ่ง n x n อาร์เรย์ 2d โดยที่แต่ละรายการเป็นคู่ในรูปแบบ (0, สตริงว่าง)
สำหรับฉันอยู่ในช่วง n-1 ถึง -1 ลดลง 1 ทำ
- สำหรับ j ในช่วง i+1 ถึง n ทำ
  - ถ้า s[i] เหมือนกับ s[j] และสตริงของ dp[i+1, j-1] ไม่ใช่ s[i] ดังนั้น
    - dp[i, j] :=สร้างคู่ (องค์ประกอบแรกของ dp[i+1, j-1] + 2, s[i])
  - มิฉะนั้น
    - dp[i, j] :=เลือกระหว่าง (dp[i+1, j], dp[i, j-1], dp[i+1,j-1]) ซึ่งองค์ประกอบแรกของคู่มีค่าสูงสุด
  - คืนค่าองค์ประกอบแรกของคู่ที่เก็บไว้ที่ dp[0, n-1]

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

ตัวอย่าง

def solve(s):
   n = len(s)
   dp = [[(0, '')]*n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(i+1, n):
         if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
            dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
         else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
   return dp[0][n-1][0]
print(solve('efeffe'))

อินพุต

'efeffe'