[Leetcode]InterleavingString

[解题思路]

DP

Let F(i, j) denote if s1 of length i and s2 of length j could form s3 of
lenght i+j, then we have four cases:
(1) F(i, j) = F(i-1,
j)                             
if s1[i-1] == s3[i+j-1] && s2[j-1] != s3[i +j -1]
(2) F(i, j) = F(i,
j-1)                    
         if s1[i-1] != s3[i+j-1]  &&
s2[j-1] == s3[i +j -1]
(3) F(i, j) = F(i-1, j) || F(i,
j-1)             if
s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i +j -1]
(4) F(i, j) =
false                    
              if s1[i-1] != s3[i+j-1]
&& s2[j-1] != s3[i +j -1]

但是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;

ref: http://www.cnblogs.com/feiling/p/3296057.html  
&& http://fisherlei.blogspot.com/2012/12/leetcode-interleaving-string.html