aboutsummaryrefslogtreecommitdiff
path: root/interleaving_string.c
blob: 2d93759c1c3a8eaa93985bf7f02157703c9911fe (plain)
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
62
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
}