สตริงย่อยพาลินโดรมที่ยาวที่สุด (Longest Palindromic Substring) ใน Python

สมมติว่าเรามีสตริง S เราต้องหาสตริงย่อยพาลินโดรมที่ยาวที่สุดใน S เราสมมติว่าความยาวของสตริง S คือ 1000 ดังนั้นถ้าสตริงคือ "BABAC" สตริงย่อยพาลินโดรมที่ยาวที่สุดคือ "BAB"

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

• กำหนดเมทริกซ์สี่เหลี่ยมจัตุรัสขนาดเท่าความยาวสตริง และเติมด้วย False
• ตั้งค่า diagonal หลักเป็น true ดังนั้น DP[i, i] = True สำหรับ i ทั้งหมดจาก 0 ถึง order - 1
• start := 0
• for l ใน range 2 ถึง length of S + 1
  • for i ใน range 0 ถึง length of S - l + 1
    • end := i + l
    • ถ้า l = 2 แล้ว
      • ถ้า S[i] = S[end - 1] แล้ว
        • DP[i, end - 1] = True, max_len := l, และ start := i
    • อื่นๆ
      • ถ้า S[i] = S[end - 1] และ DP[i + 1, end - 2] แล้ว
        • DP[i, end - 1] = True, max_len := l, และ start := i
• คืนค่าสตริงย่อยจาก index start ถึง start + max_len

ตัวอย่าง (Python)

ลองดูการทำงานต่อไปนี้เพื่อเข้าใจดีขึ้น:

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

ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))

Input

"ABBABBC"

Output

"BBABB"