Check if a string is a valid shuffle of two distinct strings

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. It may be assumed that there is no common character between A and B , C is said to be a valid shuffle A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.



EXAMPLE 1:
Input: str1 = "AB",  str2 = "CD", str 3=CADB
Output: 1
    CADB is a valid shuffle of AB and CD

EXAMPLE 2:

Input: str1 = "AB",  str2 = "CD"
Output:0
   CBDA is a not valid shuffle of AB and CD
because A should come before B.


method:
Pick each character of C one by one and match it with the first character in A. If it doesn’t match then match it with first character of B. If it doesn’t even match first character of B, then return false. If the character matches with first character of A, then repeat the above process from second character of C, second character of A and first character of B. If first character of C matches with the first character of B (and doesn’t match the first character of A), then repeat the above process from the second character of C, first character of A and second character of B. If all characters of C match either with a character of A or a character of B and length of C is sum of lengths of A and B, then C is an interleaving A and B.



c++ implementation:
bool isInterleave(string a, string b, string c) 
{
int i=0;int j=0;int k=0;

while(!c[k])
{
    if(a[i]==c[k])
    i++;
    
    else if(b[j]==c[k])
    j++;
    
    else
    return 0;
    
    k++;
    
}
if(a[i]||b[j])
return 0;

return 1;
}
Time Complexity: O(m+n) where m and n are the lengths of strings A and B respectively.



darkmode