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

By | 2012 年 9 月 29 日

<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);
}
};
```

## 14 thoughts on “LeetCode题目：Interleaving String，二维动态规划”

1. happyjacket

思路挺赞的，收获了一个想法——dp时看清楚有多少个独立变量（我一开始以为这个是三维的dp了T_T）
不过初始化部分有点冗余，其实它的边界可以match[0][0] = true就好了，不过match数组的下标需要做一点小变化，下面代码如果无法正常显示可以看这个链接：
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];
}
};

2. gli00001

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

3. Ice

初学者第一次碰到二维dp的题目，看了很受教。
不介意的话博客转走啦

4. Zhanrui

好像没那么复杂吧…我在找有没有不是O(n^2)的做法.

``` 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()]; } }; ```

1. 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()]; } }; ```

5. antiagainst

递归是可以过这个题的。楼主只注意了字符串头的比较，没有注意字符串尾的比较。同时考虑字符串尾可以剪掉很多不必要的分支。附我写的200ms左右过大数据的程序：

```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;
}
};
```