Algorithms and Me: Strings : Check if string in interleaved of two strings.

Given string A,B and C, find if string C is interleaved of A and B.

C is said to be interleaved if it contains all characters of A and B and order of characters in respective string is maintained.

If there are no common characters in string A and B:

int isInterleaved_iter(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;

}

If there are common characters in string A and B: Dynamic programming

isInterleaved(A,B,C)  = isInterleaved(A+1, B, C+1) // If character of C matches with character of A

                                 || isInterleaved(A, B+1,C+1) // If character of C matches with character of B

We create a two dimensional table. Table(i,j) = true only if C[i+j-1] is interleaved string if A[i] and B[j].

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 null here
Again if string A is empty, then Table(0,j) = Table(0, j-1) . With same argument above.

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[j] != 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])

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

    int len_a = strlen(a);

    int len_b = strlen(b);

    int i,j;

    int Table[len_a+1][len_b+1];

    // Initialization

 for(i=0;i<=len_a; i++){

        for(j=0;j<=len_b; j++){

         Table[i][j] = false;

        }

 }

    for(i=0;i<=len_a; i++){

        for(j=0;j<=len_b; 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 charactetr 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[len_a][len_b];

}

Recursive version

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)); 

}

Read full article from Algorithms and Me: Strings : Check if string in interleaved of two strings.