ধরুন আমাদের দুটি স্ট্রিং S এবং T আছে। আমাদের ক্রিয়াকলাপের সংক্ষিপ্ততম ক্রমটি খুঁজে বের করতে হবে যা S থেকে T পরিবর্তন করে। এখানে ক্রিয়াকলাপগুলি মূলত একটি অক্ষর মুছে ফেলা বা সন্নিবেশ করা হয়।
সুতরাং, যদি ইনপুট S ="xxxy" T ="xxyy" এর মত হয়, তাহলে আউটপুট হবে ["x", "x", "-x", "y", "+y"], এর অর্থ স্থান প্রথমে দুইটি x, তারপরে 3য় x মুছে ফেলুন, তারপর y রাখুন তারপর একটি নতুন y যোগ করুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- 505 x 505 আকারের একটি টেবিল ডিপি তৈরি করুন
- একটি ফাংশন হেল্প() সংজ্ঞায়িত করুন, এতে i, j, S, T, লাগবে
- যদি i এর আকার S এর সমান এবং j টি T এর আকারের সমান হয়, তাহলে −
- রিটার্ন dp[i, j] =0
- যদি আমি S এর আকারের সমান হয়, তাহলে −
- রিটার্ন dp[i, j] =1 + সাহায্য(i, j + 1, S, T)
- যদি T এর আকারের সমান হয়, তাহলে −
- রিটার্ন dp[i, j] =1 + সাহায্য(i + 1, j, S, T)
- যদি dp[i, j] -1 এর সমান না হয়, তাহলে −
- রিটার্ন dp[i, j]
- DontDo :=1e5, del :=0, insert :=0
- যদি S[i] T[j] এর মত হয়, তাহলে −
- DontDo :=help(i + 1, j + 1, S, T)
- del :=1 + সাহায্য(i + 1, j, S, T)
- ঢোকান :=1 + সাহায্য(i, j + 1, S, T)
- minVal :=min({dontDo, del, insert})
- রিটার্ন dp[i, j] =minVal
- একটি ফাংশন getPath() সংজ্ঞায়িত করুন, এতে i, j, S, T, curr, একটি অ্যারে ret লাগবে,
- যদি curr 0 এর সমান হয় এবং i S এর আকারের সমান হয় এবং j T এর আকারের সমান হয়, তাহলে −
- প্রত্যাবর্তন
- যদি i
- ret এর শেষে স্ট্রিং(1, S[i]) ঢোকান
- getPath(i + 1, j + 1, S, T, curr, ret)
- রিটের শেষে সন্নিবেশ ("-" কনক্যাটেনেট স্ট্রিং(1, S[i]))
- getPath(i + 1, j, S, T, curr - 1, ret)
- রিটের শেষে সন্নিবেশ ("+" কনক্যাটেনেট স্ট্রিং(1, T[j]))
- getPath(i, j + 1, S, T, curr - 1, ret)
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v) { cout << "["; for (int i = 0; i < v.size(); i++) { cout << v[i] << ", "; } cout << "]" << endl; } 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; int del = 0; int insert = 0; if (S[i] == T[j]) dontDo = help(i + 1, j + 1, S, T); del = 1 + help(i + 1, j, S, T); insert = 1 + help(i, j + 1, S, T); int minVal = min({dontDo, del, insert}); return dp[i][j] = minVal; } 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; } }; vector<string> solve(string source, string target) { return (new Solution())->solve(source, target); } main(){ string S = "xxxy", T = "xxyy"; print_vector(solve(S, T)); }
ইনপুট
"xxxy", "xxyy"
আউটপুট
[x, x, -x, y, +y, ]