# Accepted 6ms DP solution, similar with what is used in Regular Expression Matching.

• Here is my accepted c++ DP solution, 6ms:

``````class Solution {
public:
bool isInterleave(std::string s1, std::string s2, std::string s3) {
if (s1.empty())
return s2 == s3;
if (s2.empty())
return s1 == s3;
int len1 = static_cast<int>(s1.size()), len2 = static_cast<int>(s2.size()), len3 = static_cast<int>(s3.size());
if (len1 + len2 != len3)
return false;
std::vector<std::vector<int> > flag(len1 + 1, std::vector<int>(len2 + 1));
flag[0][0] = 1;
for (int i = 1; i <= len2; ++i)
flag[0][i] = flag[0][i - 1] && s2[i - 1] == s3[i - 1];
for (int i = 1; i <= len1; ++i) {
flag[i][0] = flag[i - 1][0] && s1[i - 1] == s3[i - 1];
for (int j = 1; j <= len2; ++j) {
flag[i][j] = flag[i - 1][j] && s3[i + j - 1] == s1[i - 1] ||
flag[i][j - 1] && s3[i + j - 1] == s2[j - 1];
}
}
return flag[len1][len2];
}
};
``````

The similar question is Regular Expression Matching, and here is the solution:

``````class Solution {
public:
bool isMatch(std::string s, std::string p) {
std::vector<std::vector<int> > f(s.size() + 1, std::vector<int>(p.size() + 1));
f[0][0] = 1;
for (int i = 2; i <= p.size(); ++i)
f[0][i] = p[i - 1] == '*' && f[0][i - 2];
for (int i = 1; i <= s.size(); ++i)
for (int j = 1; j <= p.size(); ++j)
f[i][j] = p[j - 1] == '*' ?
f[i][j - 2] || f[i - 1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.') :
f[i - 1][j - 1] && (p[j - 1] == s[i - 1] || p[j - 1] == '.');
return f[s.size()][p.size()];
}
};
``````

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