Untitled

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        int p = s3.length();

        if (n + m != p) {
            return false;
        }

        boolean[][][] dp = new boolean[n + 1][m + 1][p + 1];

        dp[0][0][0] = true;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 1; k <= p; k++) {
                    if (i > 0 && s1.charAt(i - 1) == s3.charAt(k - 1)) {
                        dp[i][j][k] = dp[i][j][k] || dp[i - 1][j][k - 1];
                    }
                    
                    if (j > 0 && s2.charAt(j - 1) == s3.charAt(k - 1)) {
                        dp[i][j][k] = dp[i][j][k] || dp[i][j - 1][k - 1];
                    }

                }
            }
        }

        return dp[n][m][p];

        // for (int[][] array : dp) {
        //     for (int[] arr : array) {
        //         Arrays.fill(arr, -1);
        //     }
        // }
        
        // dp[0][0][0] = 1;

        // return isInterLeave(n,m,p, s1, s2, s3, dp);
    }

    private boolean isInterLeave(int i, int j, int k, String s1, String s2, String s3, int[][][] dp) {
        if (k == 0 && i == 0 && j == 0) {
            return true;
        }

        if (k <= 0 && (i > 0 || j > 0)) {
            return false;
        }

        if (dp[i][j][k] != -1) {
            boolean val =  (dp[i][j][k] == 0) ? false : true;
            return val;
        }


        if (i > 0 && s1.charAt(i - 1) == s3.charAt(k - 1)) {
            if (isInterLeave(i - 1, j, k - 1, s1, s2, s3, dp)) {
                dp[i][j][k] = 1;
                return true;
            }
        }

        if (j > 0 && s2.charAt(j - 1) == s3.charAt(k - 1)) {
            if (isInterLeave(i, j - 1, k - 1, s1, s2, s3, dp)) {
                dp[i][j][k] = 1;
                return true;
            }
        }

        dp[i][j][k] = 0;
        return false;
    }
}