Untitled

 avatar
unknown
plain_text
a year ago
1.1 kB
5
Indexable
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        int p = s3.length();

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

        for (int[][] array : dp) {
            for (int[] arr : array) {
                Arrays.fill(arr, -1);
            }
        }
        return isInterLeave(0,0,0, s1, s2, s3);
    }

    private boolean isInterLeave(int i, int j, int k, String s1, String s2, String s3) {
        if (k == s3.length() && i == s1.length() && j == s2.length()) {
            return true;
        }

        if (k >= s3.length() && (i < s1.length() || j < s2.length())) {
            return false;
        }


        if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
            if (isInterLeave(i + 1, j, k + 1, s1, s2, s3)) {
                return true;
            }
        }

        if (j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
            if (isInterLeave(i, j + 1, k + 1, s1, s2, s3)) {
                return true;
            }
        }

        return false;
    }
}
Editor is loading...
Leave a Comment