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.

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