simple dp solution 4ms beats 52% c++


  • 2
                s1 - >
    s2          0  a  a  b
    |         0   1 
             a
             b
    

    We start with dp[0][0] as 1.
    we move in diagonal manner i.e. dp[1][0] to dp[0][1]
    then dp[2][0] to dp[1][1] to dp[0][2] ans increase s3 pointer
    Thus at each step by looking at next char we see the paths we can go on.
    We return true if bottomost right element is 1.

    public:
        bool isInterleave(string s1, string s2, string s3) {
            if(s1.size()+s2.size()!=s3.size())return false;
            if(s1.size()==0 && s2==s3)return true;
            else if(s1.size()==0 && s2!=s3)return false;
            else if(s2.size()==0 && s1==s3)return true;
            else if(s2.size()==0 && s1!=s3)return false;
            
            s1.insert(0,"0");
            s2.insert(0,"0");
            int l1=s1.length();
            int l2=s2.length();
            int l3=s3.length();
            vector<vector<int>>dp(l2+10,vector<int>(l1+10,0));
            dp[0][0]=1;
            int i3=0;
            int i1=1,j1=0;
            while(1)
            {
                int i=i1,j=j1;
                while(i>=0 && j<l1)
                {
                    if(i-1>=0 && dp[i-1][j]==1)
                        if(s3[i3]==s2[i])
                            dp[i][j]=1;
                    if(j-1>=0 && dp[i][j-1]==1)
                        if(s3[i3]==s1[j])
                            dp[i][j]=1;
                    i--,j++;
                }
                if(i1==l2-1 && j1==l1-1)break;
                i3++;
                if(i1<l2-1)
                    i1++;
                else j1++;
            }
            return dp[l2-1][l1-1];
        }
    };```

Log in to reply
 

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