Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:s1 =
"aabcc"
,s2 =
"dbbca"
,When s3 =
"aadbbbaccc"
, return false.
When s3 =
"aadbbcbcac"
, return true.
Solution:
bool isInterleave(string s1, string s2, string s3) {
int len1= s1.size();
int len2 = s2.size();
int len3 = s3.size();
if(len1+len2!=len3)
return false;
vector<vector<bool> > match(len1+1, vector<bool>(len2+1,false));
match[0][0] = true;
for(int i = 0;i<len1;i++)
{
if(s1[i]==s3[i])
match[i+1][0] = true;
else
break;
}
for(int i = 0;i<len2;i++)
{
if(s2[i]==s3[i])
match[0][i+1] = true;
else
break;
}
for(int i = 1;i<=len1;i++)
{
char c1 = s1[i-1];
for(int j = 1;j<=len2;j++)
{
char c2 = s2[j-1];
char c3 = s3[i+j-1];
if(c1==c3) // one situation is related to its previous one and current situation.
match[i][j] = match[i-1][j]||match[i][j];
if(c2==c3)
match[i][j] = match[i][j-1]||match[i][j];
}
}
return match[len1][len2];
}
No comments:
Post a Comment