समस्या विवरण
दो स्ट्रिंग्स str1 और str2 दी गई हैं। सबसे छोटी स्ट्रिंग ढूंढनी है जिसमें दोनों str1 और str2 सबसीक्वेंस (subsequence) के रूप में मौजूद हों।
सबसीक्वेंस: कुछ अक्षर हटाकर (शून्य या अधिक) प्राप्त स्ट्रिंग।
उदाहरण
इनपुट
"acab", "bac"
आउटपुट
"bacab"
व्याख्या: दोनों दी गई स्ट्रिंग्स "bacab" की सबसीक्वेंस हैं।
समाधान दृष्टिकोण (LCS + मर्ज)
- सबसे लंबी कॉमन सबसीक्वेंस (LCS) ढूंढें।
- दोनों स्ट्रिंग्स को LCS के साथ मर्ज करें: LCS के अक्षर एक बार लें, बाकी अक्षर क्रम में जोड़ें।
कार्यकारी प्रोग्राम
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
string lcs = getLCS(str1, str2);
string res = "";
int i = 0, j = 0, k = 0;
while (k < lcs.size()) {
while (i < str1.size() && str1[i] != lcs[k]) res += str1[i++];
while (j < str2.size() && str2[j] != lcs[k]) res += str2[j++];
res += lcs[k++];
i++; j++;
}
while (i < str1.size()) res += str1[i++];
while (j < str2.size()) res += str2[j++];
return res;
}
string getLCS(string s1, string s2) {
int n = s1.size(), m = s2.size();
vector> dp(n+1, vector(m+1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (s1[i-1] == s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
string lcs = "";
int i = n, j = m;
while (i > 0 && j > 0) {
if (dp[i][j] == dp[i-1][j]) i--;
else if (dp[i][j] == dp[i][j-1]) j--;
else { lcs += s1[i-1]; i--; j--; }
}
reverse(lcs.begin(), lcs.end());
return lcs;
}
};
int main() {
Solution ob;
cout << ob.shortestCommonSupersequence("acab", "bac");
return 0;
}
आउटपुट
bacab