假设我们有两个字符串str1和str2，我们必须找到同时具有str1和str2作为子序列的最短字符串。结果可能不止一个，因此我们将仅返回其中之一。
如您所知，如果从T删除一些字符（可能为0，并且从T的任何位置选择了字符）会导致字符串S，则字符串S称为字符串T的子序列。
因此，如果输入像“ acab”，“ bac”，那么输出将是“ bacab”，这是因为两个给定的字符串是此字符串的子序列。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数getLCS()，它将取s1，s2，
ret：=空字符串
n：= s1的大小，m：= s2的大小
定义一个大小为（n + 1）x（m + 1）的2D数组dp
i：= n，j：= m
s1：=在s1之前连接空白字符串
s2：=在s2之前连接空白字符串
对于初始化i：= 1，当i <= n时，更新（将i增加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]的最大值
对于初始化j：= 1，当j <= m时，更新（将j增加1），-
而（i为非零且j为非零），则执行-
（将j减1）
忽略以下部分，跳至下一个迭代
（将i减1）
忽略以下部分，跳至下一个迭代
如果dp [i，j]与dp [i-1，j]相同，则-
如果dp [i，j]与dp [i，j-1]相同，则-
ret：= ret + s1 [i]
（将i减1）
（将j减1）
反转数组ret
返回ret
从主要方法中执行以下操作-
s3：= getLCS(str1,str2)
ret：=空字符串，i：= 0，j：= 0，k：= 0
当k <s3的大小时，做-
ret：= ret + str2 [j]
（将j增加1）
忽略以下部分，跳至下一个迭代
ret：= ret + str1 [i]
（将i增加1）
忽略以下部分，跳至下一个迭代
如果i <str1的大小且str1 [i]不等于s3 [k]，则-
如果j <str2的大小且str2 [j]不等于s3 [k]，则-
ret：= ret + s3 [k]
（将i，j，k加1）
当我<str1的大小时，-
ret：= ret + str1 [i]
（将i增加1）
当j <str2的大小时，执行-
ret：= ret + str2 [j]
（将j增加1）
返回ret
让我们看下面的实现以更好地理解-
#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