Interleaved Strings - dp recursion

interleaved_strings.cpp

bool isInterleave(string A, string B, string C) 
{
    if(A.length()==0 && B.length()==0 && C.length()==0){
        return true;
    }
    if(C.length() < A.length()+B.length()){
        return false;
    }
    bool ans = false;
    if(A.length()!=0 && A[0]==C[0]){
        ans = isInterleave(A.substr(1),B,C.substr(1));
    }
    if(B.length()!=0 && B[0]==C[0]){
        ans = ans || isInterleave(A,B.substr(1),C.substr(1));
    }
    return ans;
}

Given three strings A, B and C your task is to complete the function isInterleave which returns true if C is an interleaving of A and B else returns false. C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.

Input:
2
YX X XXY
XY X XXY
Output
0
1

We could think of using LCS of A and C and find the common subsequence, and then compare the remaining subsequence of C with B. But LCS is a greedy approach and gives only the first match it finds. In this question, C can have multiple different subsequences of A and thus we have to probe all of them. Hence an exhausting recursive approach is required.

To handle all cases, two possibilities need to be considered.
a) If first character of C matches with first character of A, we move one character ahead in A and C and recursively check.
b) If first character of C matches with first character of B, we move one character ahead in B and C and recursively check.
If any of the above two cases is true, we return true, else false.
Thus if at any time we find that all strings are empty then we return true.