Description#
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.
A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.
Example 1:
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.
Example 2:
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"
Constraints:
1 <= str1.length, str2.length <= 1000str1 and str2 consist of lowercase English letters.
Solutions#
Solution 1#
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
27
28
29
30
| 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])
|
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
27
28
29
30
31
32
33
34
| 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();
}
}
|
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
27
28
29
30
31
32
33
| class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
int m = str1.size(), n = str2.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int 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]);
}
}
int i = m, j = n;
string ans;
while (i || j) {
if (i == 0)
ans += str2[--j];
else if (j == 0)
ans += str1[--i];
else {
if (f[i][j] == f[i - 1][j])
ans += str1[--i];
else if (f[i][j] == f[i][j - 1])
ans += str2[--j];
else
ans += str1[--i], --j;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};
|
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| 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)
}
|
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
27
28
29
30
31
32
33
34
| function shortestCommonSupersequence(str1: string, str2: string): string {
const m = str1.length;
const n = str2.length;
const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let 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] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
let ans: string[] = [];
let i = m;
let j = n;
while (i > 0 || j > 0) {
if (i === 0) {
ans.push(str2[--j]);
} else if (j === 0) {
ans.push(str1[--i]);
} else {
if (f[i][j] === f[i - 1][j]) {
ans.push(str1[--i]);
} else if (f[i][j] === f[i][j - 1]) {
ans.push(str2[--j]);
} else {
ans.push(str1[--i]);
--j;
}
}
}
return ans.reverse().join('');
}
|
