Description: We have to check whether a given string S is an interleaving of 2 other strings S1 and S2. A string S is said to be an interleaving of S1 and S2 is it contains all characters of S1 and S2 and order of characters in individual strings is preserved.

 
If video does not load, Click here
 
Example:
Input:

S1:”cat”

S2:”dog”

S: ”cdatog ” 

Output:

Interleaving is present.

Algorithm:

1.Intialize variables ‘i’(index for S1), ‘j’(index for S2) and ‘k’(Index for S) as 0.

 

2.Scan through the string S using index ‘k’ and check following conditions:

-If the value of S[k] is equal to S1[i] and the value of ‘i’ is less than the length of the string S1, increment ‘i’ by 1.

-Else If, the value of S[k] is equal to S2[j] and the value of ‘j’ is less than the length of the string S2, increment ‘j’ by 1.

-Else, break out of the loop as NO INTERLEAVING is present.

 

3.If the 2nd step gives positive results, check if

                  Length(S1) +Length(S2)==Length(S)

 

If equal,  INTERLEAVING IS PRESENT.

 

Implementation in C:

/* The following function returns 1 if S is an interleaving of S1 and S2, else returns 0*/
int check_interleaved (char *S1, char *S2, char *S)
{
    /*Loop through all characters of S.*/
    while (*S != 0)
    {
        /*Match first character of S with first character of S1*/
        if (*S1 == *S)
            S1++;
 
        /*Match first character of S with first character of S2*/
        else if (*S2 == *S)
            S2++;
 
        else
            return 0;
         
        /*move S to next*/
        S++;
    }
 
    /*If S1 or S2 still have some characters, then length of S is smaller than sum of lengths of S1 and S2, so return 0.*/
  
  if (*S1 || *S2)
        return 0;
 
    return 1;
}

 

Note: The above method fails if S1 and S2 have some characters in common. For example, if string S1 = “AAB”, string S2 = “AAC” and string S = “AACAAB”, then the above method will return false.

Go to top