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.
S: ”cdatog ”
Interleaving is present.
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
If equal, INTERLEAVING IS PRESENT.
/* 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)
/*Match first character of S with first character of S2*/
else if (*S2 == *S)
/*move S to next*/
/*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)
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.