C++ এ দূরত্ব সম্পাদনা করুন

ধরুন আমাদের কাছে দুটি শব্দ আছে word1 এবং word2, আমাদেরকে word1 থেকে word2 পর্যন্ত কনসার্ট করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ক্রিয়াকলাপ খুঁজে বের করতে হবে৷ অপারেশন তিন ধরনের হতে পারে, এগুলো হল একটি অক্ষর সন্নিবেশ করানো, একটি অক্ষর মুছে ফেলা এবং একটি অক্ষর প্রতিস্থাপন করা। তাই যদি ইনপুট স্ট্রিংগুলি "মূল্যায়ন" এবং "ফ্লাকচুয়েট" হয়, তাহলে ফলাফল হবে 5৷

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

• n :=w1 এর আকার, m :=w2 এর আকার,

• n + 1

  আকারের একটি অ্যারে ডিপি তৈরি করুন

• আমি 0 থেকে n

  পরিসরে

  • dp[i] :=m + 1

    আকারের নতুন অ্যারে

  • 0 থেকে m −

    পরিসরে j-এর জন্য

    • dp[i, j] :=0

    • যদি i =0, তাহলে dp[i,j] =j

    • অন্যথায় যখন j =0, তারপর dp[i, j] :=i

• w1 :=ফাঁকা স্থান এবং সংযুক্তি w1, w2 :=ফাঁকা স্থান এবং সংযুক্ত w2

• আমি 1 থেকে n

  রেঞ্জের মধ্যে

  • 1 থেকে m

    পরিসরে j এর জন্য

    • যদি w1[i] w2[j] না হয়, তাহলে dp[i, j] :=1 + min of dp[i – 1, j], dp[i, j - 1], dp[i – 1, j – 1]

    • অন্যথায় dp[i, j] :=dp[i – 1, j – 1]

• dp[n, m]

  ফেরত দিন

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minDistance(string w1, string w2) {
      int n = w1.size();
      int m =w2.size();
      int** dp = new int*[n+1];
      for(int i =0;i<=n;i++){
         dp[i] = new int[m+1];
         for(int j=0;j<=m;j++){
            dp[i][j]=0;
            if(i==0)dp[i][j]=j;
            else if(j==0)dp[i][j] = i;
         }
      }
      w1 = " " + w1;
      w2 = " " + w2;
      for(int i =1;i<=n;i++){
         for(int j = 1;j<=m;j++){
            if(w1[i] !=w2[j]){
               dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i1][j-1]});
            } else {
               dp[i][j] = dp[i-1][j-1];
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.minDistance("fluctuate", "evaluate"));
}

ইনপুট

"fluctuate"
"evaluate"

আউটপুট

5