C++-এ Delete Operations for Two Strings

এই সমস্যায় দুটি স্ট্রিং দেওয়া থাকলে, সেগুলো একই করার জন্য ন্যূনতম কতটি ডিলিশন অপারেশন লাগবে তা বের করতে হবে। প্রতিটি ধাপে যেকোনো একটি স্ট্রিং থেকে একটা ক্যারেক্টার ডিলিট করা যায়।

উদাহরণ: "sea" এবং "eat" -> আউটপুট 2। 's' এবং 't' ডিলিট করতে হবে।

সমাধানের পদ্ধতি (DP - Edit Distance Variant)

এটি LCS (Longest Common Subsequence) সমস্যার ভেরিয়েন্ট। ন্যূনতম ডিলিশন = len(s1) + len(s2) - 2 * LCS(s1, s2)। অথবা সরাসরি DP:

dp[i][j] = s1[0..i-1] এবং s2[0..j-1] একই করার জন্য ন্যূনতম ডিলিশন।
বেস: dp[0][j] = j, dp[i][0] = i।
ট্রানজিশন:
- যদি s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]।
- অন্যথায়: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])।

উদাহরণ (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) dp[i][0] = i;
        for (int j = 1; j <= m; j++) dp[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << ob.minDistance("sea", "eat");
    return 0;
}

ইনপুট

"sea" "eat"