Chuỗi con palindrome 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 palindrome dài nhất trong S. Giả định độ dài chuỗi S là 1000. Ví dụ, nếu chuỗi là "BABAC", thì chuỗi con palindrome dài nhất là "BAB".

Để giải quyết bài toán này, chúng ta làm theo các bước sau:

• Định nghĩa một ma trận vuông bậc bằng độ dài chuỗi, điền False
• Đặt các phần tử đường chéo chính = True, tức DP[i, i] = True với mọi i từ 0 đến bậc - 1
• start := 0
• for l trong range 2 đến độ dài S + 1
  • for i trong range 0 đến độ dài 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
    • ngược lại
      • 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ề chuỗi con từ chỉ số start đến start + max_len

Ví dụ (Python)

Hãy xem 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"))

Input

"ABBABBC"

Output

"BBABB"