โปรแกรมหาจำนวนวิธีแบ่งสตริงเป็นพาลินโดรมใน Python

มีสตริง s หาจำนวนวิธีแบ่งสตริงให้ทุกชิ้นเป็นพาลินโดรม

เช่น s="xyyx" ให้ 3: ["x","yy","x"], ["x","y","y","x"], ["xyyx"]

ขั้นตอนการแก้ปัญหา

• DP: table[i] = จำนวนวิธีแบ่ง s[:i]
• table[0]=1
• สำหรับ i=1..n: วน j=0..i-1 ถ้า s[j:i] เป็นพาลินโดรม table[i] += table[j]
• คืน table[n]

ตัวอย่างโค้ด

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

อินพุต

"xyyx"

เอาต์พุต

3