# C++ dp solution with explanation

• First tried brute force backtracking, it's obvious will not be accepted.

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
if(n1 + n2 != n3) return false;
return isInterleaveHelper(s1, 0, n1, s2, 0, n2, s3, 0, n3);
}

bool isInterleaveHelper(string &s1, int i1, int n1, string &s2, int i2, int n2, string &s3, int i3, int n3){
if(i1 == n1 && i2 == n2 && i3 == n3) return true;
if(i1 < n1 && s1[i1] == s3[i3] && isInterleaveHelper(s1, i1 + 1, n1, s2, i2, n2, s3, i3 + 1, n3)) return true;
if(i2 < n2 && s2[i2] == s3[i3] && isInterleaveHelper(s1, i1, n1, s2, i2 + 1, n2, s3, i3 + 1, n3)) return true;
else return false;
}
};
``````

Then it comes to dp solution. I first built a two dimension dp table, with drawing the path displayed below. Because it's interleaving, so certain order still needs to maintain, so that's why for a valid path, it can only go right or down, so that's why `dp[i1][i2]` is depending on `dp[i1 - 1][i2]` and `dp[i1][i2 - 1]`. After discovering the transition rule to get `dp[i1][i2]`, we just need to record true or false in the dp table. `dp[i1][i2]` means if `s3.substr(0, i1 + i2)` can be formed by `s1.substr(0, i1)` interleaving `s2.substr(0, i2)`;

``````s3 = “aadbbcbcac”
a	    a	    b	    c	   c
0	 1	    2	    3	    4	   5

0	“”→	 a  →   aa
↓
↓	    ↓
↓		↓
↓

a	5
``````

code, O(n1n2) space, and O(n1n2)time, it's much better than the brute force now.

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = (int)s1.size(), n2 = (int)s2.size(), n3 = (int)s3.size();
if(n1 + n2 != n3) return false;

vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1, false));
dp[0][0] = true;

for(int i2 = 1; i2 <= n2; i2++) dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
for(int i1 = 1; i1 <= n1; i1++) dp[i1][0] = dp[i1 - 1][0] && s1[i1 - 1] == s3[i1 - 1];

for(int i1 = 1; i1 <= n1; i1++){
for(int i2 = 1; i2 <= n2; i2++){
dp[i1][i2] = (dp[i1 - 1][i2] && s1[i1 - 1] == s3[i1 + i2 - 1]) || (dp[i1][i2 - 1] && s2[i2 - 1] == s3[i1 + i2 - 1]);
}
}

return dp[n1][n2];
}
};``````

• Great explanation. Thank you so much!

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