# LeetCode题目：Interleaving String，二维动态规划

<br>

`bool isInterleaving(string &s1, int len1, string &s2, int len2, string &s3, int len3);`

```isInterleaving(s1,len1,s2,len2,s3,len3)
=   (s3.lastChar == s1.lastChar) && isInterleaving(s1,len1 - 1,s2,len2,s3,len3 - 1)
||(s3.lastChar == s2.lastChar) && isInterleaving(s1,len1,s2,len2 - 1,s3,len3 - 1)
```

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.

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
//create indicator
vector > match(s1.size() + 1, vector(s2.size() + 1, false));
//initialization the first row and the first column
match[0][0] = true;
for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
char c1 = s1[l1 - 1];
char c3 = s3[l1 - 1];
if (c1 == c3) {
match[l1][0] = true;
} else
break;
}
for( int l2 = 1; l2 <= s2.size(); ++ l2 ) {
char c2 = s2[l2 - 1];
char c3 = s3[l2 - 1];
if (c2 == c3) {
match[0][l2] = true;
} else
break;
}
//work through the rest of matrix using the formula
for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
char c1 = s1[l1 - 1];
for( int l2 = 1 ; l2 <= s2.size() ; ++ l2 ) {
char c2 = s2[l2 - 1];
int l3 = l1 + l2;
char c3 = s3[l3 - 1];
if (c1 == c3) {
match[l1][l2] = match[l1 - 1][l2] || match[l1][l2];
}
if (c2 == c3) {
match[l1][l2] = match[l1][l2 - 1] || match[l1][l2];
}
}
}
//the last element is the result
return match[s1.size()][s2.size()];
}
};
```

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
int i1 = 0;
int i2 = 0;
for(int i3 = 0 ; i3 < s3.size(); ++i3) {
if(i1 < s1.size() && s1[i1] == s3[i3]) {
++i1;
} else if (i2 < s2.size() && s2[i2] == s3[i3]) {
++i2;
} else
return false;
}
return true;
}
};
```

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
vector visited(s3.size(),false);
int i3 = 0;
for( int i1 = 0; i1 < s1.size() ; ++i1 ) {
bool match = false;
while(i3 < s3.size()) {
if(s3[i3] == s1[i1]) {
visited[i3 ++] = true;
match = true;
break;
}
++i3;
}
if(!match)
return false;
}
i3 = 0;
for( int i2 = 0; i2 < s2.size() ; ++i2 ) {
bool match = false;
while(i3 < s3.size()) {
if (visited[i3]) {
++i3;
continue;
}
if(s3[i3 ++] == s2[i2]) {
match = true;
break;
}
}
if(!match)
return false;
}
return true;
}
};
```

```class Solution {
public:
bool isInterleave(string &s1,int i1, string &s2, int i2, string &s3, int i3) {
if(i1 == s1.size() && i2 == s2.size() && i3 == s3.size())
return true;
bool match = false;
if(i1 < s1.size() && s1[i1] == s3[i3]) {
match = isInterleave(s1, i1 + 1, s2, i2, s3, i3 + 1);
}
if (!match && i2 < s2.size() && s2[i2] == s3[i3]) {
match = isInterleave(s1, i1, s2, i2 + 1, s3, i3 + 1);
}
return match;
}
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
return isInterleave(s1,0,s2,0,s3,0);
}
};
```

## “LeetCode题目：Interleaving String，二维动态规划”上的14条回复

happyjacket说：

http://paste.ubuntu.com/14204947/

class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int L1 = s1.size(), L2 = s2.size(), L3 = s3.size();
if (L3 != L1 + L2)
return false;

s1 = ‘ ‘ + s1, s2 = ‘ ‘ + s2, s3 = ‘ ‘ + s3;
vector<vector > match(L1+1, vector(L2+1, false));
match[0][0] = true;
for (int i = 0; i <= L1; ++i)
for (int j = 0; j <= L2; ++j) {
int k = i + j;
if (k == 0)
continue;
if (s1[i] == s3[k])
match[i][j] = match[i][j] || match[i-1][j];
if (s2[j] == s3[k])
match[i][j] = match[i][j] || match[i][j-1];
}
return match[L1][L2];
}
};

gli00001说：

match[l1][l2] = match[l1 – 1][l2] || match[l1][l2];
|| match[l1][l2]貌似多余啊。

`||match[l1][l2]`

happyjacket说：

[…] LeetCode题目：Interleaving String，二维动态规划 […]

Ice说：

[…] s2 to match s3[p3-1]. This algorithm encounters time expiration for some large data set. Some one here claims he can elaborate it to pass all the test cases. But I do not bother to think of […]

Zhanrui说：

``` class Solution { public: bool isInterleave(string s1, string s2, string s3) { // Start typing your C/C++ solution below // DO NOT write int main() function int i, j; if(s1.size() + s2.size() != s3.size()) return false; vector<vector > f(s1.size() + 1, vector(s2.size() + 1)); for(i = 0; i <= s1.size(); i++){ for(j = 0; j 0 and s2[j-1] == s3[i+j-1] and f[i][j-1] or i>0 and s1[i-1] == s3[i+j-1] and f[i-1][j]); } } return f[s1.size()][s2.size()]; } }; ```

Zhanrui说：

antiagainst说：

```class Solution {
public:
string str1, str2, str3;
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (s3.size() != s1.size() + s2.size()) return false;
str1 = s1;
str2 = s2;
str3 = s3;
return check(0, s1.size() - 1, 0, s2.size() - 1, 0, s3.size() - 1);
}
bool check(int p1, int q1, int p2, int q2, int p3, int q3) {
if (p3 > q3) return true;
if (p1 > q1) {
while (p3 <= q3 && str3[p3] == str2[p2]) p2++, p3++;
if (p3  q2) {
while (p3 <= q3 && str3[p3] == str1[p1]) p1++, p3++;
if (p3 <= q3) return false;
return true;
}

if (str3[p3] == str1[p1]) {
if (str3[q3] == str1[q1] && check(p1 + 1, q1 - 1, p2, q2, p3 + 1, q3 - 1)) return true;
if (str3[q3] == str2[q2] && check(p1 + 1, q1, p2, q2 - 1, p3 + 1, q3 - 1)) return true;
}
if (str3[p3] == str2[p2]) {
if (str3[q3] == str1[q1] && check(p1, q1 - 1, p2 + 1, q2, p3 + 1, q3 - 1)) return true;
if (str3[q3] == str2[q2] && check(p1, q1, p2 + 1, q2 - 1, p3 + 1, q3 - 1)) return true;
}
return false;
}
};
```
antiagainst说：

Oops, 贴出来的代码被吃掉了一部分……

Monamona说：