# DP_C++_3ms_Accepted_Time: O(mn)_Space: O(mn)

• Use 2-dimension vector to check each char in s3 and to find out whether it could be connected by its previous char in s1 or s2.
(I tried to use O(m+n) space but failed, is it possible for O(m+n) ? ; - ) )

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size();//rows
int n2 = s2.size();//cols
int n3 = s3.size();
if(n1 + n2 != n3){return false;}
else if(n1 == 0 && n2 == 0 && n3 == 0) return true;
else if(s1[0] != s3[0] && s2[0] != s3[0]) return false;

int dp[n1+1][n2+1] = {0};

for(int i = 1; i <= n1; ++i){
if(s1[i-1] == s3[i-1]){dp[i][0] = 1;}
else{break;}
}

for(int j = 1; j <= n2; ++j){
if(s2[j-1] == s3[j-1]){dp[0][j] = 1;}
else{break;}
}

int ptr = 0;// for s3
for(int i = 1; i <= n1; ++i){
for(int j = 1; j <= n2; ++j){
ptr = i + j;
if(s3[ptr - 1] == s1[i - 1]){dp[i][j] = dp[i-1][j] || dp[i][j];}
if(s3[ptr - 1] == s2[j - 1]){dp[i][j] = dp[i][j-1] || dp[i][j];}
//if(dp[i][j]) ptr++; no need. because we use i and j as the variable.
}
}
return dp[n1][n2];
}
};
``````

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