সমস্যা বিবরণ
দুটি শব্দ S এবং T দেওয়া থাকলে, S-কে T-তে রূপান্তর করার জন্য ন্যূনতম অপারেশন সংখ্যা বের করতে হবে। অপারেশন তিন ধরনের: ক্যারেক্টার ইনসার্ট, ডিলিট, রিপ্লেস। এটাকে লেভেনস্টাইন দূরত্ব (Levenshtein Distance) বলা হয়।
উদাহরণ: "evaluate" → "fluctuate" = ৫ অপারেশন।
সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)
n = s.size(),m = t.size()।dp[n+1][m+1]টেবিল তৈরি করুন।- বেস কেস:
dp[0][j] = j(j ইনসার্ট),dp[i][0] = i(i ডিলিট)। - স্ট্রিংগুলোর শুরুতে স্পেস যোগ করুন (1-বেসড ইন্ডেক্স)۔
- i = 1 থেকে n, j = 1 থেকে m লুপ চালান:
- যদি
s[i] != t[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]রিটার্ন করুন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDistance(string s, string t) {
int n = s.size();
int m = t.size();
vector> dp(n + 1, vector(m + 1, 0));
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
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];
}
};
int main() {
Solution ob;
cout << ob.minDistance("fluctuate", "evaluate");
return 0;
}
ইনপুট ও আউটপুট
ইনপুট: "fluctuate", "evaluate"
আউটপুট: 5
জটিলতা
- সময়: O(n × m)
- স্থান: O(n × m) — دو সারি রেখে O(min(n,m)) করা সম্ভব
