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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
// 1092. Shortest Common Supersequence
#include "leetcode.h"
/*
* 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 supersequence if string 't' if deleting some
* number of characters from 't' (possibly 0) results in string 's'.
*/
void reverse(char *s) {
int n = strlen(s);
for (int i = 0; i < n / 2; i++) {
char tmp = s[i];
s[i] = s[n - 1 - i];
s[n - 1 - i] = tmp;
}
}
char *shortestCommonSupersequence(char *s1, char *s2) {
int m = strlen(s1), n = strlen(s2);
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++) {
if (!i)
dp[i][j] = j;
else if (!j)
dp[i][j] = i;
else if (s1[i - 1] == s2[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = 1 + fmin(dp[i - 1][j], dp[i][j - 1]);
}
char *ans = calloc(4000, sizeof(char));
int idx = 0, i = m, j = n;
while (i && j) {
if (s1[i - 1] == s2[j - 1]) {
ans[idx++] = s1[i - 1];
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
ans[idx++] = s2[j - 1];
j--;
} else {
ans[idx++] = s1[i - 1];
i--;
}
}
while (i)
ans[idx++] = s1[i - 1], i--;
while (j)
ans[idx++] = s2[j - 1], j--;
reverse(ans);
return ans;
}
int main() {
char *s11 = "abac", *s21 = "cab", *s12 = "aaaaaaaa", *s22 = "aaaaaaaa";
printf("%s\n", shortestCommonSupersequence(s11, s21)); // expect: cabac
printf("%s\n", shortestCommonSupersequence(s12, s22)); // expect: aaaaaaaa
}
|