Chương trình đếm số cách phân chia chuỗi thành các palindrome bằng Python

Cho chuỗi s. Đếm số cách phân chia s thành các đoạn mà mỗi đoạn là palindrome.

Ví dụ: s="xyyx" → 3 (["x","yy","x"], ["x","y","y","x"], ["xyyx"]).

Giải thuật

• Quy hoạch động: table[i] = số cách phân chia tiền tố độ dài i.
• table[0] = 1.
• Với i = 1..n: với j = 0..i-1, nếu s[j:i] là palindrome → table[i] += table[j].
• Trả về table[n].

Ví dụ minh họa

class Solution:
    def solve(self, s):
        n = len(s)
        table = [1] + [0] * n
        for i in range(n + 1):
            for j in range(i):
                sub = s[j:i]
                if sub == sub[::-1]:
                    table[i] += table[j]
        return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

Đầu vào

"xyyx"

Đầu ra

3