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.
» Solve this problem
[解题思路]
第一个想法是merge sort或许可以做。
1: bool isInterleave(string s1, string s2, string s3) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(s3.size() != (s1.size() + s2.size()))
5: {
6: return false;
7: }
8: int i =0, j= 0, k=0;
9: while(i< s1.size() && j< s2.size())
10: {
11: if(s1[i] == s3[k])
12: {
13: i ++;
14: }
15: else if(s2[j] == s3[k])
16: {
17: j++;
18: }
19: else
20: {
21: return false;
22: }
23: k++;
24: }
25: while(i< s1.size())
26: {
27: if(s1[i] == s3[k])
28: {
29: i++;k++;
30: }
31: else
32: {
33: return false;
34: }
35: }
36: while(j<s2.size())
37: {
38: if(s2[j] == s3[k])
39: {
40: j++;k++;
41: }
42: else
43: {
44: return false;
45: }
46: }
47: return true;
48: }
但是merge sort没法考虑两个字符串的组合顺序问题。当处理{"C","CA", "CAC"}的时候，就不行了。
最后还是得用DP。对于
s1 = a1, a2 ........a(i-1), ai
s2 = b1, b2, .......b(j-1), bj
s3 = c1, c3, .......c(i+j-1), c(i+j)
定义 match[i][j] 意味着，S1的(0, i)和S2的(0,j)，匹配与S3的(i+j)
如果 ai == c(i+j), 那么 match[i][j] = match[i-1][j]， 等价于如下字符串是否匹配。
s1 = a1, a2 ........a(i-1)
s2 = b1, b2, .......b(j-1), bj
s3 = c1, c3, .......c(i+j-1)
同理，如果bj = c(i+j), 那么match[i][j] = match[i][j-1];
所以，转移方程如下：
Match[i][j]
= (s3.lastChar == s1.lastChar) && Match[i-1][j]
||(s3.lastChar == s2.lastChar) && Match[i][j-1]
初始条件：
i=0 && j=0时，Match[0][0] = true;
i=0时， s3[j] = s2[j], Match[0][j] |= Match[0][j-1]
s3[j] != s2[j], Match[0][j] = false;
j=0时， s3[i] = s1[i], Match[i][0] |= Match[i-1][0]
s3[i] != s1[i], Match[i][0] = false;
[Code]
1: bool isInterleave(string s1, string s2, string s3) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: bool *matchUp = new bool[s2.size() +1];
5: bool *matchDown = new bool[s2.size()+1];
6: if(s3.size() != (s1.size() + s2.size())) return false;
7: //initialize
8: matchDown[0] = true;
9: for(int i =1; i< s2.size() +1; i++)
10: {
11: if(s2[i-1] == s3[i-1])
12: matchDown[i] |= matchDown[i-1];
13: else
14: matchDown[i]= false;
15: }
16: matchUp[0] = true;
17: for(int i =1; i< s1.size() +1; i++)
18: {
19: if(s1[i-1] == s3[i-1])
20: matchUp[0] |= matchDown[0];
21: else
22: matchUp[0]= false;
23: for(int j =1;j<s2.size() +1; j++)
24: {
25: matchUp[j]=false;
26: if(s1[i-1] == s3[i+j-1])
27: {
28: matchUp[j] |= matchDown[j];
29: }
30: if(s2[j-1] == s3[i+j-1])
31: {
32: matchUp[j] |= matchUp[j-1];
33: }
34: }
35: bool* temp = matchUp;
36: matchUp = matchDown;
37: matchDown = temp;
38: }
39: return matchDown[s2.size()];
40: }
[总结]
代码实现中注意初始条件即可。用二维数组实现也可，只是浪费点空间。
代码中有个bug，程序结束时，忘了删除数组。 应该加上Delete matchUp; Delete MatchDown; 写惯了C#，再用c++，老是往最后的清理工作。
