C++ এ দুটি স্ট্রিংয়ের জন্য অপারেশন মুছুন

ধরুন আমাদের কাছে w1 এবং w2 দুটি শব্দ আছে, আমাদের w1 এবং w2 একই করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে, যেখানে প্রতিটি ধাপে আমরা যেকোন একটি স্ট্রিং থেকে একটি করে অক্ষর মুছে ফেলতে পারি। . সুতরাং ইনপুট যদি “sea” এবং “eat” এর মত হয়, তাহলে আউটপুট হবে 2, কারণ আমাদের w1 থেকে ‘s’ মুছে ফেলতে হবে, এটি হবে “ea” এবং w2 থেকে “eat” থেকে “t” মুছে ফেলতে হবে। তারপর তারা একই।

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

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

উদাহরণ(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minDistance(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] + 1;
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + 1;
      }
      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] + 1, dp[i][j - 1] + 1);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1};
   cout << (ob.minDistance("sea", "eat"));
}

ইনপুট

"sea"
"eat"

আউটপুট

2