# Regular DP solution C++

• ``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.length() + s2.length() != s3.length()) return false;
if (s1.length() == 0) return s2 == s3;
if (s2.length() == 0) return s1 == s3;
int m = s1.length();
int n = s2.length();
vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));
//dp[i][j] indicates that whether s1[0....i-1] s2[0......j-1] interleaves s3[0......i+j-1]
//to calculate dp[i][j]
//consider two case:
//if dp[i-1][j] = true; s1[i-1] == s3[i+j-1], then dp[i][j] = true
//if dp[i][j-1] = true; s2[j-1] == s3[i+j-1], then dp[i][j] = true
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
//first consider dp[i-1][j]
if (i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1]) {
dp[i][j] = true; continue;
}
//next consider dp[i][j-1]
if (j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1]) {
dp[i][j] = true;
}
}
}
return dp[m][n];
}
};``````

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