Without DP , recursion based solution


#1
bool sol(string A,string B,string C,int i,int j){
    if((C.length()-j-i)!=(A.length()-i+B.length()-j))
    return false;
    if(i==A.length()&&j==B.length())
    return true;
    else if(C[i+j]!=A[i]&&C[i+j]!=B[j])
    return false;
    else {
        while(i<A.length()&&j<B.length()){
            if(A[i]==B[j])
            return sol(A,B,C,i+1,j)||sol(A,B,C,i,j+1);
            else if(A[i]==C[i+j])
            i++;
            else if(B[j]==C[i+j])
            j++;
            else return false;
        }
        if(i<A.length()&&A.substr(i)!=C.substr(i+j))
        return false;
        else if(j<B.length()&&B.substr(j)!=C.substr(i+j))
        return false;
        else return true;
    }
}

int Solution::isInterleave(string A, string B, string C) {
    if(C.length()!=(A.length()+B.length()))
    return 0;
    return sol(A,B,C,0,0)*1;
}