LeetCode : 97. Interleaving String

[congr]

https://leetcode.com/problems/interleaving-string/

[congr]

"Hard" level question.

Great start with recursion, but it was Time Limit Exceeded. So this code should use memoization.

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.isEmpty()) return s1.isEmpty() && s2.isEmpty();
        if (s1.isEmpty()) return s2.equals(s3);
        if (s2.isEmpty()) return s1.equals(s3);

        return inter(s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), 0,0,0); 
    }

    boolean inter(char[] c1, char[] c2, char[] c3, int p1, int p2, int p3) {
        if (p1 == c1.length && p2 == c2.length && p3 == c3.length) return true;
        else if (p3 == c3.length) return false;

        boolean res = false;
        if (p1 < c1.length && c1[p1] == c3[p3]) 
            res |= inter(c1, c2, c3, p1+1, p2, p3+1);
        if (p2 < c2.length && c2[p2] == c3[p3])
            res |= inter(c1, c2, c3, p1, p2+1, p3+1);

        return res;
    }
}

[congr]

Runtime: 1 ms, faster than 95.34% of Java online submissions for Interleaving String.

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.isEmpty()) return s1.isEmpty() && s2.isEmpty();
        if (s1.isEmpty()) return s2.equals(s3);
        if (s2.isEmpty()) return s1.equals(s3);

        int[][] d = new int[s1.length()][s2.length()]; 
        for (int i=0; i<d.length; i++) Arrays.fill(d[i], -1);
        return inter(s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), 0,0,0,d); 
        //return d[s1.length()-1][s2.length()-1]; // !!!!
    }

    boolean inter(char[] c1, char[] c2, char[] c3, int p1, int p2, int p3, int[][] d) {
        if (p1 == c1.length && p2 == c2.length && p3 == c3.length) return true;
        else if (p3 == c3.length) return false;

        if (p1 == c1.length) return compare(c2, c3, p2, p3);
        if (p2 == c2.length) return compare(c1, c3, p1, p3);

        if (d[p1][p2] != -1) return d[p1][p2]==1;

        boolean res = false;
        if (p1 < c1.length && c1[p1] == c3[p3])
            res |= inter(c1, c2, c3, p1 + 1, p2, p3 + 1, d);
        if (p2 < c2.length && c2[p2] == c3[p3])
            res |= inter(c1, c2, c3, p1, p2 + 1, p3 + 1, d);

        d[p1][p2] = res? 1 : 0;
        return res;
    }

    boolean compare (char[] a, char[] b, int i, int j) {
        while (a[i++] == b[j++]) if (i>=a.length || j>=b.length) break;
        return (i == a.length && j == b.length);
    }
}

[congr]

DP solution

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.isEmpty()) return s1.isEmpty() && s2.isEmpty();
        if (s1.isEmpty()) return s2.equals(s3);
        if (s2.isEmpty()) return s1.equals(s3);

        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();

        boolean[][] d = new boolean[c1.length+1][c2.length+1];
        d[0][0] = true;

        for (int i = 0; i <= c1.length; i++) {
            for (int j = 0; j <= c2.length; j++) {
                if (i != 0 && j != 0) d[i][j] = (d[i][j-1] && c2[j-1] == c3[i+j-1]) ||
                                                (d[i-1][j] && c1[i-1] == c3[i+j-1]);
                else if (j != 0) d[i][j] = d[i][j-1] && c2[j-1] == c3[i+j-1];
                else if (i != 0) d[i][j] = d[i-1][j] && c1[i-1] == c3[i+j-1];
            }
        }

        for (int i=0; i<c1.length; i++)
        System.out.println(Arrays.toString(d[i]));
        return d[c1.length-1][c2.length-1];
    }
}

"aabcc"
"dbbca"
"aadbbcbcac"

[true, false, false, false, false, false]
[true, false, false, false, false, false]
[true, true, true, true, true, false]
[false, true, true, false, true, false]
[false, false, true, true, true, true]