int sol(string &A, string &B, string &C, int ap, int bp, int cp,vector<vector<vector<int>>>&dp) {
  if (ap == A.length() && bp == B.length() && cp == C.length()) return true;
    if (ap == A.length() && bp == B.length() && cp != C.length()) return false;
    if (cp == C.length() && (ap != A.length() || bp != B.length())) return false;
    if(dp[ap][bp][cp] != -1) return dp[ap][bp][cp];
    if (ap == A.length()) {
        if (B[bp] != C[cp]) return false;
        return    dp[ap][bp][cp]= sol(A, B, C, ap, bp + 1, cp + 1,dp);
    }
    if (bp == B.length()) {
        if (A[ap] != C[cp]) return false;
        return   dp[ap][bp][cp]= sol(A, B, C, ap + 1, bp, cp + 1,dp);
    }

    if (A[ap] == C[cp] && B[bp] == C[cp]) {
        return    dp[ap][bp][cp]=sol(A, B, C, ap, bp + 1, cp + 1,dp) || sol(A, B, C, ap + 1, bp, cp + 1,dp);
    } else if (A[ap] == C[cp] && B[bp] != C[cp]) {
        return    dp[ap][bp][cp]= sol(A, B, C, ap + 1, bp, cp + 1,dp);
    } else if (A[ap] != C[cp] && B[bp] == C[cp]) {
        return    dp[ap][bp][cp]=sol(A, B, C, ap, bp + 1, cp + 1,dp);
    } else if (A[ap] != C[cp] && B[bp] != C[cp]) {
        return    dp[ap][bp][cp]=sol(A,B,C,ap,bp+1,cp,dp) || sol(A,B,C,ap+1,bp,cp,dp);
    }

    return    dp[ap][bp][cp]=false;
}

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

   vector<vector<vector<int>>> dp(A.size()+2,vector<vector<int>>(B.size()+2,vector<int>(C.size()+2,-1)));
    return sol(A,B,C,0,0,0,dp);
}