ধরুন আমাদের str1 এবং str2 দুটি স্ট্রিং আছে, আমাদেরকে সবচেয়ে ছোট স্ট্রিংটি খুঁজে বের করতে হবে যাতে str1 এবং str2 উভয়ই রয়েছে। একাধিক ফলাফল থাকতে পারে, তাই আমরা তাদের মধ্যে শুধুমাত্র একটি ফেরত দেব।
যেমন আপনি জানেন যে একটি স্ট্রিং S কে স্ট্রিং T এর একটি অনুবর্তন বলা হয় যদি T থেকে কিছু সংখ্যক অক্ষর মুছে ফেলা হয় (সম্ভবত 0, এবং অক্ষরগুলি T থেকে যে কোনো জায়গায় বেছে নেওয়া হয়) ফলে স্ট্রিং S হয়।
সুতরাং, যদি ইনপুটটি "acab", "bac" এর মত হয়, তাহলে আউটপুট হবে "bacab", এর কারণ হল দুটি প্রদত্ত স্ট্রিং এর অনুগামী।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন getLCS() সংজ্ঞায়িত করুন, এটি s1, s2,
লাগবে -
ret :=খালি স্ট্রিং
-
n :=s1 এর আকার, m :=s2 এর আকার
-
আকারের একটি 2D অ্যারে dp সংজ্ঞায়িত করুন (n + 1) x (m + 1)
-
i :=n, j :=m
-
s1 :=s1 এর আগে ফাঁকা স্ট্রিং সংযুক্ত করুন
-
s2 :=s2 এর আগে ফাঁকা স্ট্রিং সংযুক্ত করুন
-
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), −
-
j শুরু করার জন্য :=1, যখন j <=m, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
-
যদি s1[i] s2[j] এর মত হয়, তাহলে −
-
dp[i, j] :=1 + dp[i - 1, j - 1]
-
-
অন্যথায়
-
dp[i, j] :=সর্বাধিক dp[i - 1, j] এবং dp[i, j - 1]
-
-
-
-
যখন (i অ-শূন্য এবং j অ-শূন্য), কর −
-
যদি dp[i, j] dp[i - 1, j] এর মত হয়, তাহলে −
-
(i 1 দ্বারা কমান)
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
যদি dp[i, j] dp[i, j - 1] এর মত হয়, তাহলে −
-
(j 1 দ্বারা কমিয়ে দিন)
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
ret :=ret + s1[i]
-
(i 1 দ্বারা কমান)
-
(j 1 দ্বারা কমিয়ে দিন)
-
-
অ্যারে রিভার্স করুন
-
রিটার্ন রিটার্ন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
s3 :=getLCS(str1, str2)
-
ret :=খালি স্ট্রিং, i :=0, j :=0, k :=0
-
যখন k
করুন -
যদি i
-
ret :=ret + str1[i]
-
(i 1 দ্বারা বাড়ান)
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
যদি j
-
ret :=ret + str2[j]
-
(j 1 দ্বারা বাড়ান)
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
ret :=ret + s3[k]
-
(i, j, k 1 দ্বারা বাড়ান)
-
-
যখন i
-
ret :=ret + str1[i]
-
(i 1 দ্বারা বাড়ান)
-
-
যখন j
করুন -
ret :=ret + str2[j]
-
(j 1 দ্বারা বাড়ান)
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2){
string s3 = getLCS(str1, str2);
string ret = "";
int i = 0;
int j = 0;
int k = 0;
while (k < s3.size()) {
if (i < str1.size() && str1[i] != s3[k]) {
ret += str1[i];
i++;
continue;
}
if (j < str2.size() && str2[j] != s3[k]) {
ret += str2[j];
j++;
continue;
}
ret += s3[k];
k++;
i++;
j++;
}
while (i < str1.size()) {
ret += str1[i];
i++;
}
while (j < str2.size()) {
ret += str2[j];
j++;
}
return ret;
}
string getLCS(string s1, string s2){
string ret = "";
int n = s1.size();
int m = s2.size();
vector<vector<int> > dp(n + 1, vector<int>(m + 1));
int i = n;
int j = m;
s1 = " " + s1;
s2 = " " + s2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
while (i && j) {
if (dp[i][j] == dp[i - 1][j]) {
i--;
continue;
}
if (dp[i][j] == dp[i][j - 1]) {
j--;
continue;
}
ret += s1[i];
i--;
j--;
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.shortestCommonSupersequence("acab", "bac"));
} ইনপুট
"acab", "bac"
আউটপুট
bacab
