diff options
Diffstat (limited to 'shortest_common_subseq.c')
-rw-r--r-- | shortest_common_subseq.c | 61 |
1 files changed, 61 insertions, 0 deletions
diff --git a/shortest_common_subseq.c b/shortest_common_subseq.c new file mode 100644 index 0000000..ddc9906 --- /dev/null +++ b/shortest_common_subseq.c @@ -0,0 +1,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 +} |