（1过，调试很久）
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
关键：设dp[i][j]表示s3的前i+j个字符可以由s1的前i个字符和s2的前j个字符交织而成
看了这句提示才写出来，中途忽略了length1 + length2 != length3的条件调试了很久
public boolean isInterleave(String s1, String s2, String s3) {
int length1 = s1.length();
int length2 = s2.length();
//s3长度可能小于s1+s2，s3.charAt(i+j-1)会溢出
int length3 = s3.length();
//设dp[i][j]表示s3的前i+j个字符可以由s1的前i个字符和s2的前j个字符交织而成
boolean[][] dp = new boolean[length1+1][length2+1];
//初始化
if (length1 + length2 != length3)
return false;
dp[0][0] = true;
for (int i=1;i<=length1;i++) {
if (dp[i - 1][0] && s1.charAt(i-1) == s3.charAt(i-1))
dp[i][0] = true;
else
dp[i][0] = false;
}
for (int i=1;i<=length2;i++) {
if (dp[0][i-1] && s2.charAt(i-1) == s3.charAt(i-1))
dp[0][i] = true;
else
dp[0][i] = false;
}
for (int i=1;i<=length1;i++) {
for (int j=1;j<=length2;j++) {
if ((dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1))) {
dp[i][j] = true;
} else {
dp[i][j] = false;
}
}
}
return dp[length1][length2];
}
参考：
s3是由s1和s2交织生成的，意味着s3由s1和s2组成，在s3中s1和s2字符的顺序是不能变化的，和子序列题型类似，这种题我们一般是用动态规划来解。
- 设dp[i][j]表示s3的前i+j个字符可以由s1的前i个字符和s2的前j个字符交织而成。
- 状态转移方程：有两种情况
- 第一个状态转移方程：
dp[i][j]= {(dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)}
dp[i-1][j]表示若s3的前i+j-1个字符能够由s1前i-1个字符和s2的前j个字符交织而成，那么只需要s1的第i个字符与s3的第i+j个字符相等（charAt索引从0开始），那么dp[i][j]=true; - 第二个状态转移方程：
dp[i][j]= {(dp[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)}
dp[i-1][j]表示若s3的前i+j-1个字符能够由s1前i个字符和s2的前j-1个字符交织而成，那么只需要s2的第j个字符与s3的第i+j个字符相等（charAt索引从0开始），那么dp[i][j]=true;
- 第一个状态转移方程：
链接：https://www.nowcoder.com/questionTerminal/4d0f94617e454e2da23e660cded4d9e8
来源：牛客网 public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if(len1+len2 !=len3){
return false;
}
char[] chs1 = s1.toCharArray();
char[] chs2 = s2.toCharArray();
char[] chs3 = s3.toCharArray();
//dp[i][j]代表 chs1[0...i] chs2[0...j]能否顺序匹配chs3[i+j]
boolean[][] dp = new boolean[len1+1][len2+1];
//初始化 s1中取0个字符 s2中取0个字符 匹配s3从0开始的0个字符 肯定匹配true
dp[0][0] = true;
//s1中取0个s2中取i个 去和s3中0+i 个匹配
for(int i = 1 ; i < len2 + 1; i ++ ){
dp[0][i] = dp[0][i-1] && chs2[i-1] == chs3[i-1];
}
//s2中取0个s1中取i个 去和s3中0+i 个匹配
for(int i = 1 ; i < len1 + 1; i ++ ){
dp[i][0] = dp[i-1][0] && chs1[i-1] == chs3[i-1];
}
for(int i = 1 ; i < len1+1 ; i ++ ){
for(int j = 1 ; j < len2+1 ; j ++ ){
dp[i][j] = dp[i-1][j] && (chs3[i+j-1] == chs1[i-1])
|| dp[i][j-1] && (chs3[i+j-1] == chs2[j-1]);
}
}
return dp[len1][len2];
}
}