给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
感觉写了快一个月的每日一题，对于算法设计能力的搞还是有点帮助。
今天的困难级别的题目，第一眼没思路，后面想能不能用DP来做？求字符串s3可以分解局部小问题，所以说是可以用DP来写。
用DP就得想出状态转移方程，这次就差边界2和边界3没有想出，其他还是想出了，所以说我的能力应该得到了一丝丝提高。
状态方程：
边界1：dp[0][0] = true;
边界2：if i=0 : dp[0]dp[j] = s2[0-j) equals s3[0,j) 遇到false后面可以直接省略
边界3：if j=0 : dp[i]dp[0] = s1[0-i) equals s3[0,i) 遇到false后面可以直接省略
其他情况，到达（i，j）可能由（i-1,j）点向下一步，选择s1[i-1]到达；也可能由（i,j-1）点向右一步，选择s2[j-1]到达；
dp[i,j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])
该题类似于走迷宫找出口，可以将s1和s2抽象为两个坐标轴。
题目 当然还可以用DFS来写，不过时间可能超时，所以得加记忆化，详见「手画图解」DFS回溯 及其优化
下面试DP解法。
public class Main {
public static void main(String[] args) {
String s1 = "db";
String s2 = "b";
String s3 = "cbb";
System.out.println(isInterleave(s1, s2, s3));
}
public static boolean isInterleave(String s1, String s2, String s3) {
int s1_length = s1.length();
int s2_length = s2.length();
int s3_length = s3.length();
if (s1_length + s2_length != s3_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++) {
if (s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0]) {
dp[i][0] = true;
}
}
for (int j=1; j<=s2_length; j++) {
if (s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1]) {
dp[0][j] = true;
}
}
for (int i=1; i<=s1_length; i++) {
for (int j=1; j<=s2_length; j++) {
if ((dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1))
|| (dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1)))
dp[i][j] = true;
}
}
return dp[s1_length][s2_length];
}
}
