Solution with O(n) using memoization

int InterleaveUtil(int m,int n,int l,string A, string B, string C){

if(l < 0 && n<0 && m<0)
    return 1;
else if(l<0)
    return 0;

int i=m,j=n,k=l;
if(i>=0 && j>=0){
    if(A[i] == C[k] && B[j]==C[k]){
        return (InterleaveUtil(i-1,j,k-1,A,B,C) || InterleaveUtil(i,j-1,k-1,A,B,C));
    }
    else if(A[i] == C[k]){
        return InterleaveUtil(i-1,j,k-1,A,B,C);
    }
    else if(B[j]==C[k]){
        return InterleaveUtil(i,j-1,k-1,A,B,C);
    }
    else
        return 0;
}
else if( i>=0){
    while(i>=0){
        if(A[i] == C[k]){
            i--;
            k--;
        }
        else
            return 0;
    }
    if(k>=0)
        return 0;
    return 1;
    
}
else if( j>=0){
    while(j>=0){
        if(B[j] == C[k]){
            j--;
            k--;
        }
        else
            return 0;
    }
    if(k>=0)
        return 0;
    return 1;
}
else
    return 1;
return 0;

}

int Solution::isInterleave(string A, string B, string C) {

int m =A.size();
int n =B.size();
int l =C.size();
if(m+n<l)
    return 0;
return InterleaveUtil(m-1,n-1,l-1,A,B,C);

}

Click here to start solving coding interview questions