Chuỗi con Palindromic dài nhất trong Python

Giả sử chúng ta có một chuỗi S. Chúng ta phải tìm chuỗi con palindromic dài nhất trong S. Chúng ta giả sử rằng độ dài của chuỗi S là 1000. Vì vậy, nếu chuỗi là "BABAC" , thì chuỗi con palindromic dài nhất là “BAB”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau

• Xác định một ma trận vuông có thứ tự giống như độ dài của chuỗi và điền nó bằng Sai
• Đặt các phần tử đường chéo chính là true, do đó DP [i, i] =True cho tất cả các i từ 0 đến thứ tự - 1
• start:=0
• cho l trong phạm vi 2 đến độ dài của S + 1
  • cho tôi trong phạm vi từ 0 đến độ dài của S - l + 1
    • end:=i + l
    • nếu l =2, thì
      • nếu S [i] =S [end - 1], thì
        • DP [i, end - 1] =True, max_len:=l và start:=i
    • nếu không thì
      • nếu S [i] =S [end - 1] và DP [i + 1, end - 2], thì
        • DP [i, end - 1] =True, max_len:=l và start:=i
• trả về một chuỗi con từ bắt đầu chỉ mục đến bắt đầu + max_len

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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"))

Đầu vào

"ABBABBC"

Đầu ra

"BBABB"