diff options
author | Jack Sangdahl <[email protected]> | 2025-02-28 00:34:55 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-28 00:34:55 -0700 |
commit | 1bb2da19c46df3878ed2993e0da4c961f94622e1 (patch) | |
tree | 1f487a9ddd450a78d1ac12b7438231689fe393c4 /shortest_common_subseq.c | |
parent | a1bd06c84b438b48a6c01fb1b14d74571752cf50 (diff) | |
download | leetcode-1bb2da19c46df3878ed2993e0da4c961f94622e1.tar.gz leetcode-1bb2da19c46df3878ed2993e0da4c961f94622e1.zip |
1092. shortest common supersequence
Diffstat (limited to 'shortest_common_subseq.c')
-rw-r--r-- | shortest_common_subseq.c | 99 |
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; } |