class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
}
};
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 <= 1000str1 和 str2 都由小写英文字母组成。原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 10.5 MB, 提交时间: 2023-03-28 09:29:36
func shortestCommonSupersequence(str1 string, str2 string) string {
m, n := len(str1), len(str2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if str1[i-1] == str2[j-1] {
f[i][j] = f[i-1][j-1] + 1
} else {
f[i][j] = max(f[i-1][j], f[i][j-1])
}
}
}
ans := []byte{}
i, j := m, n
for i > 0 || j > 0 {
if i == 0 {
j--
ans = append(ans, str2[j])
} else if j == 0 {
i--
ans = append(ans, str1[i])
} else {
if f[i][j] == f[i-1][j] {
i--
ans = append(ans, str1[i])
} else if f[i][j] == f[i][j-1] {
j--
ans = append(ans, str2[j])
} else {
i, j = i-1, j-1
ans = append(ans, str1[i])
}
}
}
for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return string(ans)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
java 解法, 执行用时: 17 ms, 内存消耗: 45 MB, 提交时间: 2023-03-28 09:29:22
class Solution {
public String shortestCommonSupersequence(String str1, String str2) {
int m = str1.length(), n = str2.length();
int[][] f = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
int i = m, j = n;
StringBuilder ans = new StringBuilder();
while (i > 0 || j > 0) {
if (i == 0) {
ans.append(str2.charAt(--j));
} else if (j == 0) {
ans.append(str1.charAt(--i));
} else {
if (f[i][j] == f[i - 1][j]) {
ans.append(str1.charAt(--i));
} else if (f[i][j] == f[i][j - 1]) {
ans.append(str2.charAt(--j));
} else {
ans.append(str1.charAt(--i));
--j;
}
}
}
return ans.reverse().toString();
}
}
python3 解法, 执行用时: 344 ms, 内存消耗: 22.9 MB, 提交时间: 2023-03-28 09:29:00
# 动态规划+构造
# f[i][j] 字符串str1的前i个字符和str2的前j个字符的最长公共子序列的长度
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
m, n = len(str1), len(str2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
f[i][j] = f[i - 1][j - 1] + 1
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1])
ans = []
i, j = m, n
while i or j:
if i == 0:
j -= 1
ans.append(str2[j])
elif j == 0:
i -= 1
ans.append(str1[i])
else:
if f[i][j] == f[i - 1][j]:
i -= 1
ans.append(str1[i])
elif f[i][j] == f[i][j - 1]:
j -= 1
ans.append(str2[j])
else:
i, j = i - 1, j - 1
ans.append(str1[i])
return ''.join(ans[::-1])