# A 4 ms C++ solution, DP

• For example: s1="ab", s2="cd" ,s3="acdb"
Initialized matrix: mp[][]

``````? _ c d
_ 1 0 0
a 0 0 0
b 0 0 0
``````

To the grid mp[i][j], if it's above grid or left grid is '1', look for whether it's represent letter (to mp[0][1], when it's left grid is 1, it's represent letter is 'c' now) == s3[i+j-1]. If true, change this grid into 1.

``````bool isInterleave(string s1, string s2, string s3)
{
if (s3.size() != (s1.size() + s2.size()))
return 0;
int nrow = s1.size();
int ncol = s2.size();
vector<int> v(ncol + 1, 0);
vector<vector<int>> mp(nrow + 1, v);
mp[0][0] = 1;
int i, j;
for (i = 0; i <= nrow; ++i)
{
for (j = 0; j <= ncol; ++j)
{
if (i>0 && mp[i - 1][j])
{
if (s1[i - 1] == s3[i + j - 1])
mp[i][j] = 1;
}
if (j>0 && mp[i][j - 1])
{
if (s2[j - 1] == s3[i + j - 1])
mp[i][j] = 1;
}
}
}
return mp[nrow][ncol];
}
``````

It's looks like also can use BFS to solve this problem for when mp[i][j]=1, extend it's right and below grid check whether the grid's represent letter == s3[i+j].

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