Interleaving Strings DP solution

First made a basic recursive formula for the problem and then saved various states in map to avoid recalculations.

map< pair<int,int>,bool > mp;

    bool chk ( string A, string B, string C, int a, int b , int c ){

        if ( b==-1 && c==-1 ) return 1;
        bool forB = 0, forC = 0;
        if ( b>=0 && A[a]==B[b] ){
            if ( mp.find({a-1,b-1})!=mp.end() ) forB = mp[{a-1,b-1}];
            else {
                forB = chk (A,B,C,a-1,b-1,c);
                mp[{a-1,b-1}] = forB;
            }
        }
        if ( c>=0 && A[a]==C[c] ){
            if ( mp.find({a-1,b})!=mp.end() ) forC = mp[{a-1,b}];
            else {
                forC = chk (A,B,C,a-1,b,c-1);
                mp[{a-1,b}] = forC;
            }
        }
        return forB|forC;

    }

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

        mp.clear();
        int ans =  chk ( A,B,C,A.length()-1,B.length()-1,C.length()-1);
        return ans;

    }
Click here to start solving coding interview questions