সি++-এ স্ট্রিং রূপান্তরের জন্য ইনসার্ট/ডিলিট অপারেশন সিকোয়েন্স বের করা

সমস্যা বিবরণ

দুটি স্ট্রিং S এবং T দেওয়া আছে। S-কে T-এ রূপান্তর করার জন্য ন্যূনতম ইনসার্ট/ডিলিট অপারেশন সিকোয়েন্স বের করতে হবে।

উদাহরণ: S = "xxxy", T = "xxyy" → আউটপুট ["x", "x", "-x", "y", "+y"]। অর্থাৎ প্রথম দুটি x রাখুন, ৩য় x ডিলিট করুন, y রাখুন, নতুন y যোগ করুন।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (এডিট ডিস্ট্যান্স) + পাথ রিকভারি:

1. dp[i][j] = S[i:]-কে T[j:]-এ রূপান্তরের ন্যূনতম অপারেশন।
2. রিকারেন্স:
   • S[i] == T[j]: dp[i][j] = dp[i+1][j+1] (ম্যাচ)
   • dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1]) (ডিলিট বা ইনসার্ট)
3. পাথ রিকভারি: dp টেবিল দিয়ে ব্যাকট্র্যাক করে অপারেশন সিকোয়েন্স বানান।

উদাহরণ কোড

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

int dp[505][505];

class Solution {
public:
    int help(int i, int j, string& S, string& T) {
        if (i == S.size() && j == T.size()) return dp[i][j] = 0;
        if (i == S.size()) return dp[i][j] = 1 + help(i, j+1, S, T);
        if (j == T.size()) return dp[i][j] = 1 + help(i+1, j, S, T);
        if (dp[i][j] != -1) return dp[i][j];
        int dontDo = 1e5, del = 0, ins = 0;
        if (S[i] == T[j]) dontDo = help(i+1, j+1, S, T);
        del = 1 + help(i+1, j, S, T);
        ins = 1 + help(i, j+1, S, T);
        return dp[i][j] = min({dontDo, del, ins});
    }
    void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
        if (curr == 0 && i == S.size() && j == T.size()) return;
        if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i+1][j+1] == curr) {
            ret.push_back(string(1, S[i]));
            getPath(i+1, j+1, S, T, curr, ret);
        } else if (dp[i+1][j] + 1 == curr) {
            ret.push_back("-" + string(1, S[i]));
            getPath(i+1, j, S, T, curr-1, ret);
        } else {
            ret.push_back("+" + string(1, T[j]));
            getPath(i, j+1, S, T, curr-1, ret);
        }
    }
    vector<string> solve(string S, string T) {
        memset(dp, -1, sizeof dp);
        vector<string> ret;
        int x = help(0, 0, S, T);
        getPath(0, 0, S, T, x, ret);
        return ret;
    }
};

int main() {
    string S = "xxxy", T = "xxyy";
    Solution ob;
    for (auto& s : ob.solve(S, T)) cout << s << ", ";
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "xxxy", "xxyy"

আউটপুট: [x, x, -x, y, +y]