aboutsummaryrefslogtreecommitdiff
path: root/shortest_common_subseq.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-28 00:34:55 -0700
committerJack Sangdahl <[email protected]>2025-02-28 00:34:55 -0700
commit1bb2da19c46df3878ed2993e0da4c961f94622e1 (patch)
tree1f487a9ddd450a78d1ac12b7438231689fe393c4 /shortest_common_subseq.c
parenta1bd06c84b438b48a6c01fb1b14d74571752cf50 (diff)
downloadleetcode-1bb2da19c46df3878ed2993e0da4c961f94622e1.tar.gz
leetcode-1bb2da19c46df3878ed2993e0da4c961f94622e1.zip
1092. shortest common supersequence
Diffstat (limited to 'shortest_common_subseq.c')
-rw-r--r--shortest_common_subseq.c99
1 files changed, 62 insertions, 37 deletions
diff --git a/shortest_common_subseq.c b/shortest_common_subseq.c
index ddc9906..a245596 100644
--- a/shortest_common_subseq.c
+++ b/shortest_common_subseq.c
@@ -8,49 +8,74 @@
* 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;
+struct letters {
+ int len;
+ int att;
+};
+
+void check(char *str1, char *str2, struct letters **list, int i, int j) {
+ if (list[i][j].len)
+ return;
+ if (str1[i] == str2[j]) {
+ check(str1, str2, list, i + 1, j + 1);
+ list[i][j].len = list[i + 1][j + 1].len + 1;
+ list[i][j].att = -1;
+ } else {
+ check(str1, str2, list, i + 1, j);
+ int k = j + 1;
+ while (str2[k] != str1[i] && str2[k] != '\0')
+ k++;
+ if (str2[k] == '\0') {
+ list[i][j].len = list[i + 1][j].len + 1;
+ list[i][j].att = 0;
+ return;
+ } else
+ check(str1, str2, list, i, k);
+ if (list[i + 1][j].len + 1 < k - j + list[i][k].len) {
+ list[i][j].len = list[i + 1][j].len + 1;
+ list[i][j].att = 0;
+ } else {
+ list[i][j].len = k - j + list[i][k].len;
+ list[i][j].att = k - j;
+ }
}
}
-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--;
+char *shortestCommonSupersequence(char *str1, char *str2) {
+ int n1 = strlen(str1), n2 = strlen(str2);
+ struct letters **list =
+ (struct letters **)malloc((n1 + 1) * sizeof(struct letters *));
+ for (int i = 0; i < n1; i++) {
+ list[i] = (struct letters *)calloc(n2 + 1, sizeof(struct letters));
+ list[i][n2].len = n1 - i + 1;
+ }
+ list[n1] = (struct letters *)malloc((n2 + 1) * sizeof(struct letters));
+ for (int i = 0; i < n2; i++) {
+ list[n1][i].len = n2 - i + 1;
+ list[n1][i].att = 1;
+ }
+ list[n1][n2].len = 1;
+ check(str1, str2, list, 0, 0);
+ char *ans = (char *)malloc(list[0][0].len * sizeof(char));
+ int cnt = 0, m = 0, n = 0;
+ while (list[m][n].len != 1) {
+ if (list[m][n].att == -1) {
+ ans[cnt] = str1[m];
+ cnt++, m++, n++;
+ } else if (!list[m][n].att) {
+ ans[cnt] = str1[m];
+ cnt++, m++;
} else {
- ans[idx++] = s1[i - 1];
- i--;
+ for (int k = list[m][n].att; k; k--) {
+ ans[cnt] = str2[n];
+ cnt++, n++;
+ }
}
}
- while (i)
- ans[idx++] = s1[i - 1], i--;
- while (j)
- ans[idx++] = s2[j - 1], j--;
- reverse(ans);
+ ans[cnt] = '\0';
+ for (int i = 0; i <= n1; i++)
+ free(list[i]);
+ free(list);
return ans;
}