题目要求:
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
简单解释下，判断s3是否由s1和s2交替组成，即s3前n位字符由s1的前 n-i 位字符和 s2的前 i 位字符组成。
这是个典型的动态规划问题。我们保留一个二维数组 dp,
dp[i][j] 表示 s3 的前 i+j 位 字符 是否由 s1 的前 i 位 和 s2的前 j 位组成。
在已知dp[i-1][j] 和dp[i][j-1]的情况下,欲求dp[i][j],只需思考s3的第 i+j 位字符 来自 s1 的第 i 个字符 还是 s2的第 j 个字符,以及是否相等。
所以其递推公式为:dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1]
- 全部代码
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length()) return false;
boolean[][]dp = new boolean[s1.length()+1][s2.length()+1];
//初始化边界
dp[0][0] = true;
for (int i = 1; i <=s1.length() ; i++) {
dp[i][0] = s3.charAt(i-1) == s1.charAt(i-1) ? dp[i-1][0]:false;
}
for (int i = 1; i <=s2.length() ; i++) {
dp[0][i] = s3.charAt(i-1) == s2.charAt(i-1) ? dp[0][i-1]:false;
}
for (int i = 1; i <=s1.length() ; i++) {
for (int j = 1; j <=s2.length() ; j++) {
char v3 = s3.charAt(i+j-1);
boolean v1 = v3 == s1.charAt(i-1) ? dp[i-1][j]:false;
boolean v2 = v3 == s2.charAt(j-1) ? dp[i][j-1]:false;
dp[i][j] = v1 || v2;
}
}
return dp[s1.length()][s2.length()];
}
