পাইথনের পরবর্তী অংশ থেকে প্যালিনড্রোমের দৈর্ঘ্য সর্বাধিক করার জন্য প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং আছে, s এবং t। আমরা নিম্নলিখিত পদ্ধতিতে একটি স্ট্রিং তৈরি করতে চাই -

s থেকে কিছু অ-খালি অনুগামী সাব1 নির্বাচন করুন।
টি থেকে কিছু অ-খালি অনুগামী সাব2 নির্বাচন করুন।
স্ট্রিং তৈরি করতে সাব1 এবং সাব2কে সংযুক্ত করুন।

আমাদের সবচেয়ে দীর্ঘতম প্যালিনড্রোমের দৈর্ঘ্য খুঁজে বের করতে হবে যা বর্ণিত পদ্ধতিতে গঠিত হতে পারে। যদি আমরা কোনো প্যালিনড্রোম তৈরি করতে না পারি, তাহলে 0 ফেরত দিন।

সুতরাং, যদি ইনপুটটি s ="hillrace" t ="cargame" এর মত হয়, তাহলে আউটপুট হবে 7 কারণ আমরা s থেকে "race" এবং r থেকে "car" নিতে পারি, তাই "racecar" হল প্যালিনড্রোম যার দৈর্ঘ্য 7। .

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

n :=s এর আকার, m :=t এর আকার
শব্দ :=s + t
dp :=আকারের একটি 2D অ্যারে তৈরি করুন (n+m) x (n+m) এবং 0 দিয়ে পূরণ করুন
i এর জন্য রেঞ্জ (n + m - 1) থেকে 0, 1 দ্বারা হ্রাস করুন, করুন
- j-এর জন্য i থেকে n + m - 1 পরিসরে, করুন
  - যদি আমি j এর মত হয়, তাহলে
    - dp[i, j] :=1
  - অন্যথায় যখন শব্দ[i] শব্দ[j] এর মত হয়, তাহলে
    - dp[i, j] :=2 + dp[i + 1, j - 1]
  - অন্যথায়,
    - dp[i, j] =সর্বাধিক dp[i + 1, j] এবং dp[i, j - 1]
উত্তর :=0
আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
- j-এর জন্য m - 1 থেকে -1 পরিসরে, 1 দ্বারা হ্রাস করুন, করুন
  - যদি s[i] t[j] এর মত হয়, তাহলে
    - ans =সর্বাধিক উত্তর এবং dp[i, n + j]
উত্তর ফেরত দিন

উদাহরণ

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

def solve(s, t):
   n, m = len(s), len(t)
   word = s + t
   dp = [[0] * (n + m) for _ in range(n + m)]

   for i in range(n + m - 1, -1,-1):
      for j in range(i, n + m):
         if i == j:
            dp[i][j] = 1
         elif word[i] == word[j]:
            dp[i][j] = 2 + dp[i + 1][j - 1]
         else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
   ans = 0
   for i in range(n):
      for j in range(m - 1, -1, -1):
         if s[i] == t[j]:
            ans = max(ans, dp[i][n + j])
   return ans

s = "hillrace"
t = "cargame"
print(solve(s, t))

ইনপুট

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]