public class _97 {
    static class Solution1{
        public boolean isInterleave(String s1, String s2, String s3) {
            return s1.length() + s2.length() == s3.length() && dfs(new Boolean[s1.length()+1][s2.length()+1],0,0,0,s1.toCharArray(),s2.toCharArray(),s3.toCharArray());
        }

        public boolean dfs(Boolean[][] dp,int i,int j,int k,char[] s1,char[] s2,char[] s3){
            if(i == s1.length && j == s2.length) return true;
            if(dp[i][j] != null) return dp[i][j];
            return dp[i][j] = ( i < s1.length && s1[i] == s3[k] && dfs(dp,i+1,j,k+1,s1,s2,s3))
                    ||(j < s2.length && s2[j] == s3[k] && dfs(dp,i,j+1,k+1,s1,s2,s3));
        }
    }

    static class Solution2{
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length() + s2.length() != s3.length()) return false;
            boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
            char[] x1 = s1.toCharArray();
            char[] x2 = s2.toCharArray();
            char[] x3 = s3.toCharArray();
            dp[0][0] = true;
            for(int i = 0;i <= x1.length;i++){
                for(int j = 0;j <= x2.length;j++){
                    if(i==0 && j==0) continue;
                    if(i == 0){
                        dp[i][j] =  dp[i][j-1] && x2[j-1] == x3[i+j-1];
                        continue;
                    }
                    if(j == 0){
                        dp[i][j] = dp[i-1][j] && x1[i-1] == x3[i+j-1];
                        continue;
                    }
                    dp[i][j] = (dp[i-1][j] && x1[i-1] == x3[i+j-1]) || (dp[i][j-1] && x2[j-1] == x3[i+j-1]);
                }
            }
            return dp[x1.length][x2.length];
        }
    }

    static class Solution3{
        public boolean isInterleave(String s1, String s2, String s3) {
            //官方给出的空间优化思路，由Solution2变化得到
            if(s1.length() + s2.length() != s3.length()) return false;
            boolean[] dp = new boolean[s2.length()+1];
            char[] x1 = s1.toCharArray();
            char[] x2 = s2.toCharArray();
            char[] x3 = s3.toCharArray();
            for(int i = 0;i <= x1.length;i++){
                for(int j = 0;j <= x2.length;j++){
                    if(i==0 && j==0) dp[j] = true;
                    if(i == 0 &&j > 0){
                        dp[j] =  dp[j-1] && x2[j-1] == x3[i+j-1];
                        continue;
                    }
                    if(j == 0 && i> 0){
                        dp[j] = dp[j] && x1[i-1] == x3[i+j-1];
                        continue;
                    }
                    if(i > 0 && j> 0) dp[j] = (dp[j] && x1[i-1] == x3[i+j-1]) || (dp[j-1] && x2[j-1] == x3[i+j-1]);
                }
            }
            return dp[x2.length];
        }
    }
}