โปรแกรมหาความยาวซับสตริงพาลินโดรมยาวที่สุดใน Python

สมมติว่าเรามีสตริง S หาความยาวของซับสตริงพาลินโดรมยาวที่สุด สมมติความยาว S ไม่เกิน 1000 ตัวอย่าง: "BABAC" → พาลินโดรมยาวสุด "BAB" ความยาว 3

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. สร้างเมทริกซ์ dp ขนาด n×n เติม False
2. ตั้งค่า diagonal: dp[i][i] = True สำหรับทุก i
3. max_length = 1, start = 0
4. วนลูปความยาว l จาก 2 ถึง n:
   • วนลูป i จาก 0 ถึง n-l:
     • end = i + l - 1
     • ถ้า l == 2:
       • ถ้า S[i] == S[end]: dp[i][end] = True, อัปเดต max_length, start
     • อื่นๆ:
       • ถ้า S[i] == S[end] และ dp[i+1][end-1]: dp[i][end] = True, อัปเดต max_length, start
5. คืนค่า max_length

ตัวอย่างโค้ด Python

class Solution(object):
    def solve(self, s):
        n = len(s)
        dp = [[False for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        max_length = 1
        start = 0
        for l in range(2, n + 1):
            for i in range(n - l + 1):
                end = i + l - 1
                if l == 2:
                    if s[i] == s[end]:
                        dp[i][end] = True
                        max_length = l
                        start = i
                else:
                    if s[i] == s[end] and dp[i + 1][end - 1]:
                        dp[i][end] = True
                        max_length = l
                        start = i
        return max_length

ob = Solution()
print(ob.solve('BABAC'))  # Output: 3

อินพุต / เอาต์พุต

Input: "ABBABBC"

Output: 5 (ซับสตริง "BBABB" หรือ "ABBBA")