LC.P1092[最短公共超序列]
题目描述
给出两个字符串 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 都由小写英文字母组成。
方法一：动态规划
先用动态规划求出两个字符串的最长公共子序列，然后根据最长公共子序列构造出最短公共超序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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]);
}
}
StringBuilder builder = new StringBuilder();
for (int i = m, j = n; i > 0 || j > 0; ) {
if (i == 0) builder.append(str2.charAt(--j));
else if (j == 0) builder.append(str1.charAt(--i));
else {
if (f[i][j] == f[i - 1][j]) builder.append(str1.charAt(--i));
else if (f[i][j] == f[i][j - 1]) builder.append(str2.charAt(--j));
else {
builder.append(str1.charAt(--i));
--j;
}
}
}
return builder.reverse().toString();
}
}
|
- 时间复杂度：$O(mn)$
- 空间复杂度：$O(mn)$
wechat
