# 0 ms c++ DP solution

• DP formula:

``````f(s1,s2,s3) = (s1[0]==s3[0] && f(s1.substr(1), s2, s3.substr(1))) ||  (s2[0]==s3[0] && f(s1, s2.substr(1), s3.substr(1)))
``````
``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size();
int n = s2.size();
vector<vector<int>> res(m+1, vector<int>(n+1, -1));
helper(res, s1, 0, s2, 0, s3);
return res[0][0] == 1;
}

bool helper(vector<vector<int>>& res, string& s1, int i, string& s2, int j, string& s3) {
int x = s1.size() - i;
int y = s2.size() - j;
int z = s3.size() - i - j;
if (x+y != z) {
res[i][j] = 0;
}
else {
if (x == 0 && y == 0) res[i][j] = 1;
else if (x == 0) res[i][j] = s2.substr(j) == s3.substr(i+j) ? 1 : 0;
else if (y == 0) res[i][j] = s1.substr(i) == s3.substr(i+j) ? 1 : 0;
}
if (res[i][j] >= 0) return res[i][j];
bool r1 = false, r2 = false;
if (s1[i] == s3[i+j]) r1 = helper(res, s1, i+1, s2, j, s3);
if (s2[j] == s3[i+j]) r2 = helper(res, s1, i, s2, j+1, s3);
res[i][j] = (r1 || r2) ? 1 : 0;
return res[i][j];
}
};
``````

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