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 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
方法一： DFS，大数据超时
class Solution {
public:
bool dfs(int i1, int i2, int i3, string &s1, string &s2, string &s3)
{
if(i1 == size1 && i2 == size2 ) return true;
if(i1 == size1){
if(s2[i2] == s3[i3])
return dfs(i1,i2+, i3+, s1, s2, s3);
else
return false;
}else if(i2 == size2){
if(s1[i1] == s3[i3])
return dfs(i1+, i2, i3+, s1, s2, s3);
else
return false ;
}else{
bool f1, f2;
if(s1[i1] == s3[i3])
{
f1 = dfs(i1+, i2, i3+, s1, s2, s3);
if(f1 == true) return true ;
}
if(s2[i2] == s3[i3])
{
f2 = dfs(i1,i2+, i3+, s1, s2, s3);
return f2;
}
return false;
}
}
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
size1 = s1.size();
size2 = s2.size();
size3 = s3.size();
if(size1 + size2 != size3 ) return false;
return dfs(,,, s1, s2, s3) ;
}
private:
int size1;
int size2;
int size3;
};
方法二： 2D 动态规划
Use match[i][j] to save if s1[i] or s2[j] are matched s3[i+j].
match[i][j] = (s3[i+j]==s1[i] && match[i-1][j])
|| (s3[i+j] ==s2[j] && match[i][j-1])
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
size1 = s1.size();
size2 = s2.size();
size3 = s3.size();
if(size1 + size2 != size3 ) return false;
vector<vector<bool>> match( size1+, vector<bool>(size2+)) ;
match[][] = true;
for(int i = ; i <= size1 ; i++)
{
if(s1[i-] == s3[i-])
match[i][] = true;
else
break;
}
for(int j = ; j <= size2 ; j++)
{
if(s2[j-] == s3[j-])
match[][j] = true;
else
break;
}
int i,j;
for(i = ; i <= size1 ; i++)
for(j = ; j <= size2; j++)
{
match[i][j] =( match[i-][j]&&s1[i-] == s3[i+j-]) ||
(match[i][j-] && s2[j-] == s3[i+j-]) ;
}
return match[size1][size2] ;
}
private:
int size1;
int size2;
int size3;
};