โปรแกรมค้นหาความยาว palindrome สูงสุดจากลำดับย่อยใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องการสร้างสตริงในลักษณะต่อไปนี้ -

• เลือก subsequence sub1 ที่ไม่ว่างบางส่วนจาก s.

• เลือก subsequence sub2 ที่ไม่ว่างบางส่วนจาก t.

• เชื่อมต่อ sub1 และ sub2 เพื่อสร้างสตริง

เราต้องหาความยาวของพาลินโดรมที่ยาวที่สุดที่สามารถเกิดขึ้นได้ในลักษณะที่อธิบายไว้ หากเราไม่สามารถสร้าง palindrome ได้ ให้คืนค่า 0

ดังนั้น ถ้าอินพุตเป็น s ="hillrace" t ="cargame" แล้วเอาต์พุตจะเป็น 7 เพราะเราสามารถเอา "race" จาก s และ "car" จาก r ได้ ดังนั้น "racecar" คือ palindrome ที่มีความยาว 7 .

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

• n :=ขนาดของ s, m :=ขนาดของ t

• คำ :=s + t

• dp :=สร้างอาร์เรย์ขนาด 2 มิติ (n+m) x (n+m) และเติมด้วย 0

• สำหรับฉันอยู่ในช่วง (n + m - 1) ถึง 0, ลดลง 1 ทำ

  • สำหรับ j ในช่วง i ถึง n + m - 1 ทำ

    • ถ้าฉันเหมือนกับ j แล้ว

      • dp[i, j] :=1

    • มิฉะนั้น เมื่อ word[i] เหมือนกับ word[j] แล้ว

      • dp[i, j] :=2 + dp[i + 1, j - 1]

    • มิฉะนั้น

      • dp[i, j] =สูงสุด dp[i + 1, j] และ dp[i, j - 1]

• ตอบ :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ

  • สำหรับ j ในช่วง m - 1 ถึง -1 ลดลง 1 ทำ

    • ถ้า s[i] เหมือนกับ t[j] แล้ว

      • ans =สูงสุดของ ans และ dp[i, n + j]

• กลับมาอีกครั้ง

ตัวอย่าง

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

def solve(s, t):
   n, m = len(s), len(t)
   word = s + t
   dp = [[0] * (n + m) for _ in range(n + m)]

   for i in range(n + m - 1, -1,-1):
      for j in range(i, n + m):
         if i == j:
            dp[i][j] = 1
         elif word[i] == word[j]:
            dp[i][j] = 2 + dp[i + 1][j - 1]
         else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
   ans = 0
   for i in range(n):
      for j in range(m - 1, -1, -1):
         if s[i] == t[j]:
            ans = max(ans, dp[i][n + j])
   return ans

s = "hillrace"
t = "cargame"
print(solve(s, t))

อินพุต

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]

ผลลัพธ์

7