//给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
//
// 示例 1:
//
// 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出: true
//
//
// 示例 2:
//
// 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出: false
// Related Topics 字符串 动态规划//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public boolean isInterleave(String s1, String s2, String s3) {//可以不是s1,s2,依次各取一个。只需要交错即可int m=s1.length();int n=s2.length();int k=s3.length();if(m+n!=k) return false;//s1前i个 s2前j个 是否满足交错 boolean---------------boolean[][] dp=new boolean [m+1][n+1];dp[0][0]=true;for (int i = 0; i <=m ; ++i) {for (int j = 0; j <=n ; ++j) {int p=i+j-1;//从0开始，因此为i-1if (i > 0) {dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));}if (j > 0) {dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)