C++ এ দুটি স্ট্রিংয়ের মধ্যে ন্যূনতম সম্পাদনা দূরত্ব খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে S এবং T দুটি শব্দ আছে, আমাদের S থেকে T তে রূপান্তর করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করতে হবে। অপারেশনগুলি তিন ধরনের হতে পারে, এইগুলি হল

• একটি অক্ষর সন্নিবেশ করান,
• একটি অক্ষর মুছুন
• একটি অক্ষর প্রতিস্থাপন করুন।

তাই যদি ইনপুট স্ট্রিংগুলি "মূল্যায়ন" এবং "ফ্লাকচুয়েট" হয়, তাহলে ফলাফল হবে 5৷

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

• n :=s এর আকার, m :=t এর আকার,

• n + 1

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

• আমি 0 থেকে n

  পরিসরে

  • dp[i] :=m + 1

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

  • j এর জন্য 0 থেকে m:

    • dp[i, j] :=0

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

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

• s :=ফাঁকা স্থান এবং সংযুক্ত s, t :=ফাঁকা স্থান এবং সংযুক্ত t

• আমি 1 থেকে n

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

  • 1 থেকে m

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

    • যদি s[i] t[j] না হয়, তাহলে dp[i, j] :=1 + মিনিট 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 s, string t) {
      int n = s.size();
      int m =t.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;
         }
      }
      s = " " + s;
      t = " " + t;
      for(int i =1;i<=n;i++){
         for(int j = 1;j<=m;j++){
            if(s[i] !=t[j]){
               dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i-1][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