[leedcode 97] Interleaving String

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        //动态规划思想，构造一个二维数组，dp[i][j]表示s1的前i位和s2的前j位是否符合要求
        //状态转移方程是dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1))||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
        //注意下标的问题，dp的规模是[len1+1][len2+1]，第dp[0][j]表示0个s1字符和j个s2字符构成字符串的是否满足要求
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();
        if(len1+len2!=len3) return false;
        boolean dp[][]=new boolean[len1+1][len2+1];
        dp[0][0]=true;
        for(int i=1;i<=len1;i++){
            dp[i][0]=dp[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);
        }
        for(int j=1;j<=len2;j++){
            dp[0][j]=dp[0][j-1]&&s2.charAt(j-1)==s3.charAt(j-1);
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1))||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
                
            }
        }
        return dp[len1][len2];
    }
}