class Solution {

     public boolean isInterleave(String s1, String s2, String s3) {

         int len1=s1.length();

         int len2=s2.length();

         int len3=s3.length();

         //若s3长度不等于s1加上s2的长度，就直接返回false

         if(len1+len2!=len3)

             return false;

         //在此处判断是否有一方为空

         if(s1.equals(""))   return s2.equals(s3);

         if(s2.equals(""))   return s1.equals(s3);

         //建立dp数组，dp[i][j]代表s1的前i个数和s2的前j个数合并起来能否构成s3的前i+j个数

         boolean [][]dp=new boolean[len1+1][len2+1];

         //初始化dp数组

         dp[0][0]=true;

         for(int i=1;i<=len1;i++)

             dp[i][0]=s3.charAt(i-1)==s1.charAt(i-1)&&dp[i-1][0];

         for(int j=1;j<=len2;j++)

             dp[0][j]=s3.charAt(j-1)==s2.charAt(j-1)&&dp[0][j-1];

         for(int i=1;i<=len1;i++)

             for(int j=1;j<=len2;j++){

                 //构造二维数组后可得，dp[i][j]可由dp[i-1][j]添加s1的第i个数

                 //或由dp[i][j-1]添加s2的第j个数得到，此时两种情况，其中一个为true即可

                 //由此得到递推式

                 dp[i][j]=(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1))

                     ||(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1));

             }

         return dp[len1][len2];

     }

 }