สตริงย่อย Palindromic ที่ยาวที่สุดใน Python

สมมติว่าเรามีสตริง S เราต้องหาสตริงย่อยพาลินโดรมที่ยาวที่สุดใน S เราถือว่าความยาวของสตริง S คือ 1,000 ดังนั้นหากสตริงคือ “BABAC” จากนั้นสตริงย่อยพาลินโดรมที่ยาวที่สุดคือ “BAB”

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

• กำหนดหนึ่งตารางเมทริกซ์ของลำดับเดียวกับความยาวของสตริง และเติมด้วย "เท็จ"
• ตั้งค่าองค์ประกอบแนวทแยงที่สำคัญเป็นจริง ดังนั้น DP[i, i] =True สำหรับ i ทั้งหมดตั้งแต่ 0 ถึงลำดับ – 1
• เริ่ม :=0
• สำหรับ l ในช่วง 2 ถึงความยาวของ S + 1
  • สำหรับ i ในช่วง 0 ถึงความยาวของ S – l + 1
    • จบ :=ผม + ล
    • ถ้า l =2 แล้ว
      • ถ้า S[i] =S[จบ - 1] แล้ว
        • DP[i, end - 1] =True, max_len :=l, และ start :=i
    • อย่างอื่น
      • ถ้า S[i] =S[end - 1] และ DP[i + 1, สิ้นสุด - 2] แล้ว
        • DP[i, end - 1] =True, max_len :=l, และ start :=i
• ส่งคืนสตริงย่อยของ from index start to 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"))

อินพุต

"ABBABBC"

ผลลัพธ์

"BBABB"