aboutsummaryrefslogtreecommitdiff
path: root/interleaving_string.c
diff options
context:
space:
mode:
Diffstat (limited to 'interleaving_string.c')
-rw-r--r--interleaving_string.c63
1 files changed, 63 insertions, 0 deletions
diff --git a/interleaving_string.c b/interleaving_string.c
new file mode 100644
index 0000000..2d93759
--- /dev/null
+++ b/interleaving_string.c
@@ -0,0 +1,63 @@
+// 97. Interleaving String
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * given strings 's1', 's2', 's3', find whether 's3' is formed by an
+ interleaving of 's1' and 's2'. an interleaving of two strings 's' and 't' isa
+ configuration where 's' and 't' are divided into 'n' and 'm' substrings
+ respectively, such that
+ s = s1 + s2 + ... + sn
+ t = t1 + t2 + ... + tm
+ |n - m| <= 1
+ The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 +
+ t3 + s3 + ...
+*/
+
+bool isInterleave(char *s1, char *s2, char *s3) {
+ int n1 = strlen(s1), n2 = strlen(s2), n3 = strlen(s3);
+ if (n1 + n2 != n3)
+ return false;
+ if (!n1) {
+ if (!strcmp(s2, s3))
+ return true;
+ else
+ return false;
+ }
+ if (!n2) {
+ if (!strcmp(s1, s3))
+ return true;
+ else
+ return false;
+ }
+ if (s3[n3 - 1] != s1[n1 - 1] && s3[n3 - 1] != s2[n2 - 1])
+ return false;
+ if (s3[0] != s1[0] && s3[0] != s2[0])
+ return false;
+ bool **dp = malloc((n1 + 1) * sizeof(bool *));
+ for (int i = 0; i <= n1; i++)
+ dp[i] = calloc(n2 + 1, sizeof(bool));
+ dp[0][0] = true;
+ for (int i = 1; i <= n1; i++)
+ dp[i][0] = (dp[i - 1][0] == true && (s1[i - 1] == s3[i - 1]));
+ for (int i = 1; i <= n2; i++)
+ dp[0][i] = (dp[0][i - 1] == true && (s2[i - 1] == s3[i - 1]));
+ for (int i = 1; i <= n1; i++) {
+ for (int j = 1; j <= n2; j++) {
+ if ((s1[i - 1] == s3[i + j - 1]) && dp[i - 1][j] == true)
+ dp[i][j] = true;
+ else if ((s2[j - 1] == s3[i + j - 1]) && dp[i][j - 1] == true)
+ dp[i][j] = true;
+ }
+ }
+ return dp[n1][n2];
+}
+
+int main() {
+ char s11[] = {"aabcc"}, s21[] = {"dbbca"}, s31[] = {"aadbbcbcac"};
+ char s12[] = {"aabcc"}, s22[] = {"dbbca"}, s32[] = {"aadbbbaccc"};
+ printf("%d\n", isInterleave(s11, s21, s31)); // expect: 1
+ printf("%d\n", isInterleave(s12, s22, s32)); // expect: 0
+}