# Check if string is interleaved of two strings

Given three strings A,B and C, find if C string is interleaved of two strings. A and B. C is said to be interleaved if it contains all the characters of A and B and order of characters in respective strings is maintained. For example string C in figure is interleaved string of A and B.

# Find if string is interleaved of two strings

Simple algorithm to find if a string is interleaved of two other string is to start checking length of C as length of A + length of B. If it is not true return false (why?).

If length criteria passes, check first character of C and A. If they match, move to second character of C and A. Keep B at first character. If character in A does not match with character in C, check if first character of C and B match, if they do, then move to second character of C and B. A remains at first character.

Once done, repeat above steps with next characters of strings, while character in C matches character in A or B. If both current character in C does not match with any of the current characters in A and B, return false.

With above algorithm, with each comparison, problem reduces to smaller size, with C with length N-1, one of A or B with M-1. From the description, it is clear that recursion can be used to solve interleaving problem.

```isInterleaved(A,B,C)  = isInterleaved(A+1, B, C+1)
|| isInterleaved(A, B+1,C+1)
```

What shall be base case for above recursion?
If end of C is reached, all characters in C are checked, return true if all characters in other two strings are also considered. If not returned false.
Other way, if both string are A and B are fully considered and there are still characters left in C to be considered, then return false. (This case is anyways caught at length check).

### Recursive Implementation of interleaved strings algorithm

```
#include <stdio.h>
#include <string.h>
#define true 1
#define false 0;

int isInterleaved(char *c, char *a, char *b){

if(!(*c) && !(*a) && !(*b))
return true;

if(*c == '\0'){
return false;
}
// if character of a and c match
return ((*c == *a) && isInterleaved(c+1,a+1,b)) ||
// if character of b and c match
((*c == *b) && isInterleaved(c+1,a,b+1));
}

int main(void) {
char *c = "abxycdz";
char *a = "abcd";
char *b = "xyz";
if(isInterleaved(c,a,b)){
printf("\n String is interleaved");
}
else{
printf("\n String is not interleaved");
}
return 0;
}
```

### Iterative implementation is as follows

```#include <stdio.h>
#include <string.h>
#define true 1
#define false 0;

int isInterleaved(char *c, char *a, char *b){

while(*c != '\0'){
if(*c == *a){
a++;
}
else if(*c == *b){
b++;
}
else{
return false;
}
c++;
}
if(*a != '\0' || b != '\0')
return false;

return true;
}

int main(void) {
char *c = "abxycdz";
char *a = "abcd";
char *b = "xyz";
if(isInterleaved(c,a,b)){
printf("\n String is interleaved");
}
else{
printf("\n String is not interleaved");
}
return 0;
}
```

Iterative implementation will not work with input with common characters in string A and B, for example A = XXY and B = XXZ and if C = XXZXXY will return false.

Complexity of iterative implementation will be linear O(N), N being length of string C, where as complexity of recursive solution will b O(2N) but it does not fail in when two strings have common character.

## Dynamic programming approach to interleaved strings problem

Look closely and notice that many subproblems are being calculated again and again. Recursion tree for input A = XXY and B = XXZ and C = XXZXXY

Looking at the recursion tree, it is clear that if results of subproblems are stored, they need not be calculated again and again. Create a two dimensional table. Table(i,j) = true only if C[i+j-1] is interleaved string if A[i] and B[j]. Empty string is interleaved of two other strings so, Table[0][0] = true
If one of the strings was empty: Table(i,0) = A[i] == C[i] && Table(i-1, 0) that is to say if till i-1 characters C was interleaved of A, then for ith character it will be true if ith character matches ith character of A. Note that B is empty. Again if string A is empty, then Table(0,j) = Table(0, j-1). With these base cases, we can fill table bottom up as follows

```Table(i,j) = Table(i-1,j)  if (A[i] == C[i+j]) && (B[j] != C[i+j])
Table(i,j) = Table(i,j-1) (B[i] == C[i+j])&& (A[i] != C[i+j])
Table(i,j) = Table(i-1,j) || Table(i, j-1) if (A[i] == C[i+j]) && (B[j] == C[i+j])```

## Dynamic programming solution to find if string is interleaved of two strings

```#include <stdio.h>
#include <string.h>
#define true 1
#define false 0;
int isInterleaved(char *c, char *a, char *b){

int lenA = strlen(a);
int lenB = strlen(b);
int i,j;

int Table[lenA+1][lenB+1];
// Initialization
for(i=0; i<=lenA; i++){
for(j=0; j<=lenB; j++){
Table[i][j] = false;
}
}
for(i=0; i<=lenA; i++){
for(j=0; j<=lenB; j++){
// Both strings are empty
if(i==0 && j==0)
Table[i][j] = true;
// string A is empty, compare characters in C and B
if(i==0 && c[j-1] == b[j-1]){
Table[i][j] =  Table[i][j-1];
}
// string B is empty, compare characters in C and A
else if(j==0 && c[i-1] == a[i-1]){
Table[i][j] =  Table[i-1][j];
}
// Both strings are not empty
//1. If character of A matches with character of C
// but not of B
else if (a[i-1] == c[i+j-1] && b[j-1] != c[i+j-1]){
Table[i][j] = Table[i-1][j];
}
//2. If character of B matches with character of C
// but not of A
else if (a[i-1] != c[i+j-1] && b[j-1] == c[i+j-1]){
Table[i][j] = Table[i][j-1];
}
//1. If character of A matches with character of C
// and character of B also matches with C
else if (a[i-1] == c[i+j-1] && b[j-1] == c[i+j-1]){
Table[i][j] = Table[i-1][j] || Table[i][j-1];
}
}
}
return Table[lenA][lenB];
}

int main(void) {
char *c = "abxycdz";
char *a = "abcd";
char *b = "xyz";
if(isInterleaved(c,a,b)){
printf("\n String is interleaved");
}
else{
printf("\n String is not interleaved");
}
return 0;
}
```

Complexity of dynamic programming algorithm to find if a string is interleaved of two strings will be O(n2).

For more dynamic programming problems, please refer : Dynamic programming problems