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, 过程如下图所示：
|
S2 |
|||||||
|
S1 |
aadbbcbcac |
0 “” |
1 d |
2 db |
3 dbb |
4 dbbc |
5 dbbca |
|
0 “” |
T |
F(d!=a) |
F |
F |
F |
F |
|
|
1 a |
T(a==a) |
F(aa) |
F |
F |
F |
F |
|
|
2 aa |
T |
T(aad) |
T(aadb) |
||||
|
3 aab |
F(aab!=aad) |
T(aadb) |
T(aadbb) |
||||
|
4 aabc |
F |
F(aadbb) |
T(aadbbc) |
||||
|
5 aabcc |
F |
F(aadbbc) |
|||||
发现某一格dp[i][j]为true只有当其上面或左边为true才行。且需要新加入的字母与s3新添加的字母一致，True状态才能延续。
代码：
public boolean isInterleave(String s1, String s2, String s3) {
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp = new boolean[l1+1][l2+1];
for(int i=0;i<=l1;i++) {
for(int j=0;j<=l2;j++) {
if(i==0 && j==0)
dp[i][j]=true;
else if(i==0)
dp[i][j] = dp[i][j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1));
else if(j==0)
dp[i][j] = dp[i-1][j] && (s1.charAt(i-1)==s3.charAt(i+j-1));
else
dp[i][j] = (dp[i][j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1))) || (dp[i-1][j] && (s1.charAt(i-1)==s3.charAt(i+j-1)));
}
}
return dp[l1][l2];
}
简化为一维数组：
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if(l3!=(l1+l2))
return false;
boolean[] dp = new boolean[l2+1];
dp[0] = true;
for(int i=1;i<dp.length;i++)
{
dp[i] = dp[i-1] && (s2.charAt(i-1)==s3.charAt(i-1));
}
for(int i=1;i<=l1;i++)
{
for(int j=0;j<dp.length;j++)
{
if(j==0)
dp[j] = dp[j] && (s1.charAt(i-1)==s3.charAt(i-1));
else
dp[j] = (dp[j] && (s1.charAt(i-1)==s3.charAt(i+j-1))) || (dp[j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1)));
}
}
return dp[l2];
}