class Solution {
private:
    string s1,s2,s3;
    int** able;
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        if(s1.length()+s2.length()!=s3.length()) return false;
        this->s1=s1;
        this->s2=s2;
        this->s3=s3;
        able=new int*[s1.length()+1];
        for(int i=0;i<=s1.length();i++)
        {
            able[i]=new int[s2.length()+1];
            for(int j=0;j<=s2.length();j++)
                able[i][j]=0;
        }
        able[0][0]=1;
        
        return isleave(s1.length(),s2.length());
    }
    bool isleave(int index1,int index2)
    {
        if(able[index1][index2]!=0) return able[index1][index2]==1;
        if(index2>0 && isleave(index1,index2-1) && s3[index1+index2-1]==s2[index2-1])
        {
            able[index1][index2]=1;
            return true;
        }
        if(index1>0 && isleave(index1-1,index2) && s3[index1+index2-1]==s1[index1-1])
        {
            able[index1][index2]=1;
            return true;
        }
        able[index1][index2]=-1;
        return false;
    }
};