Recursive DP solution 4ms


  • 0
    K

    class Solution {

    public:

    unordered_map<string,bool> mp;
    bool isInterleave(string s1, string s2, string s3) {
        int n1=s1.size(),n2=s2.size(),n3=s3.size();
        string key=s1+","+s2+","+s3;
        if(mp.find(key)!=mp.end())
            return mp[key];
        if(n1==0)
            return mp[key]= s2==s3;
        if(n2==0)
            return mp[key]=s1==s3;
        if((!n1&&!n2)&&n3)
            return mp[key]=false;
        if(s3[0]==s1[0]&&s3[0]==s2[0])
            return mp[key]=isInterleave(s1.substr(1,n1-1),s2,s3.substr(1,n3-1))||isInterleave(s1,s2.substr(1,n2-1),s3.substr(1,n3-1));
        else if(s3[0]==s1[0]&&s3[0]!=s2[0])
                return mp[key]=isInterleave(s1.substr(1,n1-1),s2,s3.substr(1,n3-1));
        else if(s3[0]!=s1[0]&&s3[0]==s2[0])
            return mp[key]=isInterleave(s1,s2.substr(1,n2-1),s3.substr(1,n3-1));
        else if(s3[0]!=s1[0]&&s3[0]!=s2[0])
            return mp[key]=false;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.