# simple dp solution 4ms beats 52% c++

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

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];
}
};`````````

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