作者：最好的冰雪之母_227 | 来源：互联网 | 2024-09-27 11:52
Givens1,s2,s3,findwhethers3isformedbytheinterleavingofs1ands2.Forexample,Given:s1aabcc
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.
[解题思路]
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;
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
if(len3 != len1 + len2){
return false;
}
boolean[][] match = new boolean[len1 + 1][len2 + 1];
match[0][0] = true;
// j == 0
int i = 1;
while(i <= len1 && s1.charAt(i-1) == s3.charAt(i-1)){
match[i][0] = true;
i++;
}
// i == 0
int j = 1;
while(j <= len2 && s2.charAt(j-1) == s3.charAt(j-1)){
match[0][j] = true;
j++;
}
for(int m = 1; m <= len1; m++){
for(int n = 1; n <= len2; n++){
char c = s3.charAt(m + n - 1);
if(c == s1.charAt(m - 1)){
match[m][n] |= match[m-1][n];
}
if(c == s2.charAt(n - 1)){
match[m][n] |= match[m][n-1];
}
}
}
return match[len1][len2];
}
}
ref: http://www.cnblogs.com/feiling/p/3296057.html
&& http://fisherlei.blogspot.com/2012/12/leetcode-interleaving-string.html
京公网安备 11010802041100号