Chương trình kiểm tra chuỗi có thể tách thành ba palindrome trong Python

Mô tả bài toán

Cho chuỗi s. Kiểm tra có thể chia s thành 3 chuỗi con palindrome không.

Ví dụ

s = "levelpopracecar" -> True ("level", "pop", "racecar").

Giải thuật (DP)

1. Tạo bảng dp[i][j] = True nếu s[i..j] là palindrome.
2. Điền bảng từ dưới lên: dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1].
3. Duyệt i từ 1 đến n-1, j từ i+1 đến n-1: nếu dp[0][i-1], dp[i][j-1], dp[j][n-1] đều True -> trả về True.

Triển khai Python

def solve(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(n):
            if i >= j:
                dp[i][j] = True
            elif s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1]
    for i in range(1, n):
        for j in range(i + 1, n):
            if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]:
                return True
    return False

s = "levelpopracecar"
print(solve(s))

Đầu vào

"levelpopracecar"

Đầu ra

True