আমরা পাইথনে একটি প্যালিনড্রোমকে বিভক্ত করতে পারি এমন কয়েকটি উপায় খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের খুঁজে বের করতে হবে কতগুলো উপায়ে আমরা স্ট্রিংটিকে ভাগ করতে পারি যাতে প্রতিটি অংশ একটি প্যালিনড্রোম হয়।

সুতরাং, যদি ইনপুটটি s ="xyyx" এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমাদের স্প্লিট আছে যেমন:["x", "yy", "x"], ["x", "y", " y", "x"], ["xyyx"]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

• n :=s এর আকার
• টেবিল :=n + 1 আকারের একটি তালিকা এবং এটি 0 দিয়ে পূরণ করুন
• টেবিল[0] :=1
• আমি 0 থেকে n রেঞ্জের জন্য, কর
  0 থেকে i - 1 রেঞ্জের মধ্যে j-এর জন্য
  • করুন
    • sub :=s[সূচী j থেকে i]
    • যদি সাব প্যালিনড্রোম হয়, তাহলে
      • টেবিল[i] :=টেবিল[i] + টেবিল[j]
• সারণীর শেষ উপাদান ফেরত দিন

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ

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