C++ এ একটি স্ট্রিং প্যালিনড্রোম তৈরি করার জন্য ন্যূনতম সন্নিবেশের পদক্ষেপ

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

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

একটি ফাংশন lcs() সংজ্ঞায়িত করুন, এতে s, x :=s লাগবে
n :=s এর আকার
এক্স স্ট্রিং বিপরীত করুন
s :=s এর আগে concatenate space, x :=x এর আগে concatenate space
একটি 2D অ্যারে ডিপি আকারের (n + 1) x (n + 1) সংজ্ঞায়িত করুন
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
- j শুরু করার জন্য :=1, যখন j <=n, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), −
  - dp[i, j] :=সর্বাধিক dp[i – 1, j] এবং dp[i, j - 1]
  - যদি s[i] x[j] এর মত হয়, তাহলে −
    - dp[i, j] :=সর্বাধিক dp[i, j] এবং dp[i – 1, j - 1] + 1
রিটার্ন dp[n, n]
প্রধান পদ্ধতি থেকে s – lcs(s) এর রিটার্ন সাইজ

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int lcs(string s){
      string x = s;
      int n = s.size();
      reverse(x.begin(), x.end());
      s = " " + s;
      x = " " + x;
      vector < vector <int> > dp(n + 1, vector <int>(n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(s[i] == x[j]){
               dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
         }
      }
      return dp[n][n];
   }
   int minInsertions(string s) {
      return s.size() - lcs(s);
   }
};
main(){
   Solution ob;
   cout << (ob.minInsertions("mad"));
}

ইনপুট

“mad”

C++ এ একটি স্ট্রিং প্যালিনড্রোম তৈরি করার জন্য ন্যূনতম সন্নিবেশের পদক্ষেপ

উদাহরণ

ইনপুট

আউটপুট