package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月16日 15:22
 * @description: 力扣97 交错字符串
 * 思路:
 * 定义dp(i,j):表示s1的前i个元素和s2的前j个元素是否能组成交替的s3的i+j个元素
 * 如果s1的第i个元素和s3的第i+j个元素相等,那么dp[i][j]否为为true,则取决于||| 暂不分析
 */
public class Interleave {
 public static void main(String[] args) {

 }
}
class Interleave_Soulution{

 public boolean isInterleave(String s1,String s2,String s3){
 int n = s1.length();
 int m = s2.length();
 int len = s3.length();
 if(m+n != len){
 return false;
 }
 boolean [][]dp = new boolean[n+1][m+1];
 dp[0][0] = true;
 for(int i = 0; i <=len;i++){
 for(int j = 0;j <= len;j++){
 int p = i+j-1;
 if(i > 0){
 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[n][m];
 }
}