97. 交错字符串

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        /**
        动态规划
        boolean dp[i][j]表示s1的钱i个元素和s2的钱j个元素 可以交替组成s3的前i+j个元素
        dp[i][j]表示s1的钱i个元素和s2的钱j个元素 可以交替组成s3的前i+j个元素条件:
            1如果s1第i个元素和s3的弟i+j个元素相同,那么如果s1的i-1个和s2的j可以组成s3的钱i+j-1个元素 
            OR
            2如果s2第j个元素和s3的弟i+j个元素相同,那么如果s2的j-1个和s1的i可以组成s3的钱i+j-1个元素 
         */
         int m=s1.length();
         int n=s2.length();
         if(m+n!=s3.length()){
             return false;
         }
         boolean dp[][]=new boolean[m+1][n+1];  
         dp[0][0]=true;  
     
         for(int i=0;i<=m;i++){ //有可能 m ,n 都等于0
             for(int j=0;j<=n;j++){               
                 if(i>0){
                     dp[i][j]=   (s1.charAt(i-1)==s3.charAt(i+j-1)&&dp[i-1][j]);
                 }
                 if(j>0){
                         //因为i>0时dp[i][j]已经满足了 所以 dp[i][j]||
                   dp[i][j]=    dp[i][j]|| (s2.charAt(j-1)==s3.charAt(i+j-1)&&dp[i][j-1]);
               
                 }                
             }
         }
         return dp[m][n];//m-1 n-1的话 可能 m  n 都为空  就越界了  
    }
}