একটি স্ট্রিং পরীক্ষা করার জন্য প্রোগ্রাম তিনটি প্যালিনড্রোমে বিভক্ত হতে পারে বা পাইথনে নয়

ধরুন আমরা একটি স্ট্রিং s আছে. আমরা s কে তিনটি প্যালিনড্রোমিক সাবস্ট্রিংয়ে বিভক্ত করতে পারি কিনা তা পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুটটি s ="লেভেলপোপ্রেসকার" এর মতো হয়, তাহলে আউটপুটটি সত্য হবে কারণ আমরা এটিকে "লেভেল", "পপ", "রেসকার" এর মতো বিভক্ত করতে পারি, সবগুলোই প্যালিনড্রোম।

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

• n :=s

  এর আকার

• dp :=ক্রম n x n এর একটি ম্যাট্রিক্স এবং মিথ্যা দিয়ে পূরণ করুন

• n-1 থেকে 0 রেঞ্জে i এর জন্য, 1 দ্বারা হ্রাস করুন, করুন

  • 0 থেকে n - 1 রেঞ্জে j এর জন্য, করুন

    • যদি i>=j, তাহলে

      • dp[i, j] :=সত্য

    • অন্যথায় যখন s[i] s[j] এর মত হয়, তখন

      • dp[i, j] :=dp[i+1, j-1]

  • 1 থেকে n - 1 রেঞ্জের জন্য, করুন

    • i+1 থেকে n - 1 পর্যন্ত j-এর জন্য, করুন

      • যদি dp[0, i-1] এবং dp[i, j-1] এবং dp[j, n-1] সবই সত্য হয়, তাহলে

        • রিটার্ন ট্রু

• রিটার্ন ফলস

উদাহরণ

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

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

ইনপুট

"levelpopracecar"

আউটপুট

True