C++ এ দুটি স্ট্রিংয়ের জন্য ন্যূনতম ASCII মুছে ফেলার যোগফল

ধরুন আমাদের কাছে w1 এবং w2 দুটি শব্দ আছে, w1 এবং w2 একই করার জন্য আমাদের মুছে ফেলা অক্ষরগুলির সর্বনিম্ন ASCII যোগফল খুঁজে বের করতে হবে, যেখানে প্রতিটি ধাপে আমরা একটি অক্ষর মুছে ফেলতে পারি। স্ট্রিং সুতরাং ইনপুট যদি “sea” এবং “eat” এর মত হয়, তাহলে আউটপুট হবে 231, কারণ আমাদের w1 থেকে ‘s’ মুছে ফেলতে হবে, এটি হবে “ea” এবং “t” মুছে ফেলতে হবে “eat” থেকে w2। তারপর তারা একই. "eat" থেকে 't' মুছে দিলে যোগফলের সাথে 116 যোগ হয় এবং শেষে, উভয় স্ট্রিংই একই এবং 115 + 116 =231 এটি অর্জনের সর্বনিম্ন যোগফল।

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

n :=s1 এর আকার, m :=s2 এর আকার
স্ট্রিং s1 এবং s2 এর আগে একটি ফাঁকা স্থান যোগ করুন, তারপর সেই অনুযায়ী s1 এবং s2 আপডেট করুন
আকারের একটি টেবিল তৈরি করুন (n + 1) x (m + 1)
এর জন্য i :=1 থেকে m
- dp[0, i] :=dp[0, i - 1] + s2[i]
এর জন্য i :=1 থেকে n
- dp[i, 0] :=dp[i – 1, 0] + s1[i]
আমি 1 থেকে n
রিটার্ন dp[n, m]

উদাহরণ(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumDeleteSum(string s1, string s2) {
      int n = s1.size();
      int m = s2.size();
      s1 = " " + s1;
      s2 = " " + s2;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= m; i++){
         dp[0][i] = dp[0][i - 1] + s2[i];
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + s1[i];
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s1[i] == s2[j]){
               dp[i][j] = dp[i - 1][j - 1];
            }
            else{
               dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.minimumDeleteSum("sea", "eat"));
}

ইনপুট

"sea"
"eat"