ধরুন আমাদের কাছে দুটি শব্দ word1 এবং word2 আছে। আমাদের কাজ হল word1 কে word2-তে রূপান্তর করার জন্য ন্যূনতম অপারেশন সংখ্যা খুঁজে বের করা। অপারেশন তিন ধরনের হতে পারে: অক্ষর যোগ করা, অক্ষর মুছে ফেলা এবং অক্ষর প্রতিস্থাপন করা। যেমন, "evaluate" এবং "fluctuate" এর জন্য ফলাফল হবে ৫।
সমাধানের ধাপসমূহ:
n := w1-এর আকার, m := w2-এর আকার
n+1 আকারের dp অ্যারে তৈরি করুন
i = 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
w1 এবং w2-এর শুরুতে ব্ল্যাঙ্ক স্পেস যোগ করুন
i = 1 থেকে n, j = 1 থেকে m পর্যন্ত: যদি w1[i] != w2[j] হয় তবে dp[i][j] = 1 + min(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();
vector< vector<int> > dp(n + 1, vector<int>(m + 1, 0));
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
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[i-1][j-1]});
} else {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[n][m];
}
};
int main() {
Solution ob;
cout << (ob.minDistance("fluctuate", "evaluate"));
return 0;
}
ইনপুট
"fluctuate" "evaluate"
আউটপুট
5
