পাইথনে প্যালিনড্রোম স্ট্রিং বিভাজনের উপায় সংখ্যা

একটি স্ট্রিং s দেওয়া আছে। স্ট্রিংটি কতভাবে প্যালিনড্রোম সাবস্ট্রিংয়ে বিভক্ত করা যায় তা বের করতে হবে।

উদাহরণ: s = "xyyx" হলে আউটপুট ৩, কারণ ["x","yy","x"], ["x","y","y","x"], ["xyyx"]।

সমাধানের ধাপসমূহ

n := len(s)
table := n+1 আকারের তালিকা ০ দিয়ে পূরণ, table[0] = 1
i = 0 থেকে n পর্যন্ত:
- j = 0 থেকে i-1 পর্যন্ত:
  - sub := s[j:i]
  - যদি sub প্যালিনড্রোম হয় তবে table[i] += table[j]
table[-1] ফেরত দিন

উদাহরণ কোড

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"