LeetCode | 1092.最短公共超序列
给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）
示例：
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。
提示：
- 1 <= str1.length, str2.length <= 1000
- str1 和 str2 都由小写英文字母组成。
注意：子序列和子串是不同的概念
思路：分两个步骤
1. 利用动态规划求最短公共超序列的长度，并保留求解过程
2. 利用动态规划的求解过程，反推字符串
步骤1：
设字符串的长度为 m 和 n; dp[i][j] 表示字符串 str1[0, i - 1] 和 str2[0, j - 1] 的最短公共超序列的长度, i 和 j 等于 0 时，表示字符串为空。
求最短公共超序列时，遍历两个字符串，对于 str1[i] 和 str2[j] 只有三种可能的情况：
1. str1[i] == str2[j], 两个字符一样，加入超序列
2. str1[i] != str2[j], 两个字符不一样，可能是 str1[i] 加入超序列，也可能是 str2[j] 加入超序列, 因为是求最短的，选择小的加入
动态规划的状态转移方程为：
当 str1[i] == str2[j] 时：
\(dp[i][j] = dp[i - 1][j - 1] + 1\)
当 str1[i] != str2[j] 时：
\(dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1\)
边界条件：当 i 或 j 等于 0 时，字符串为空，最短公共超序列等于另一个字符串的长度
\(dp[i][j]=\left\{\begin{array}{ll}
j, & i=0 \& j<=m \\
i, & j=0 \& i<=n \\
0, & i=0 \& j=0
\end{array}\right.\)
步骤2：
经过步骤1 得到的 dp[m][n] 就是最短公共超序列的长度; 设 t1 = m, t2 = n, 从字符串的尾部开始往前遍历
如果 str1[t1 - 1] == str2[t2 - 1] 这个字符是共有的，加入到 res。
如果 str1[t1 - 1] != str2[t2 - 1], 则根据 dp[t1][t2] 是等于 dp[t1 - 1][t2] + 1 还是等于 dp[t1][t2 - 1] + 1 来判断上一个字符是 str1 的字符还是 str2 的字符
string shortestCommonSupersequence(string str1, string str2) {
int m = str1.size(), n = str2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 动态规划求最短公共超序列的长度，并保留求解过程
for (int i = 1; i <= m; i++) {
dp[i][0] = i; //当 str2 为空时，最短公共超序列长度为 str1[0, i - 1].size()
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j; //当 str1 为空时，最短公共超序列长度为 str2[0, j - 1].size()
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
string res;
int t1 = m, t2 = n;
// 利用动态规划的求解过程，逆推字符串
while (t1 > 0 && t2 > 0) {
if (str1[t1 - 1] == str2[t2 - 1]) {
res = str1[--t1] + res;
--t2;
} else if (dp[t1][t2] == dp[t1 - 1][t2] + 1) {
res = str1[--t1] + res;
} else {
res = str2[--t2] + res;
}
}
if (t1 > 0) {
res = str1.substr(0, t1) + res;
}
if (t2 > 0) {
res = str2.substr(0, t2) + res;
}
return res;
}
和上面一个思路，只是遍历字符串的顺序变了。在求最短公共超序列长度时，这个是从后往前遍历，dp[0][0] 代表的是最短公共超序列长度
string shortestCommonSupersequence(string str1, string str2) {
int n = str1.size(), m = str2.size();
// 动态规划求最短公共超序列的长度，并保留求解过程
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; ++i) {
dp[i][m] = n - i;
}
for (int i = 0; i < m; ++i) {
dp[n][i] = m - i;
}
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
if (str1[i] == str2[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
} else {
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + 1;
}
}
}
string res;
int t1 = 0, t2 = 0;
// 利用动态规划的求解过程，逆推字符串
while (t1 < n && t2 < m) {
if (str1[t1] == str2[t2]) {
res += str1[t1];
++t1;
++t2;
} else if (dp[t1 + 1][t2] == dp[t1][t2] - 1) {
res += str1[t1];
++t1;
} else if (dp[t1][t2 + 1] == dp[t1][t2] - 1) {
res += str2[t2];
++t2;
}
}
if (t1 < n) {
res += str1.substr(t1);
}
else if (t2 < m) {
res += str2.substr(t2);
}
return res;
}