2ms Java DP solution, nothing new


  • 0
    A
    int[][] mem;
    
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        mem = new int[s1.length()+2][s2.length()+2];
        for (int[] i : mem) Arrays.fill(i, -1);
        mem[s1.length()][s2.length()] = 1;
        return isInterleave(s1, 0, s2, 0, s3, 0);
    }
    
    private boolean isInterleave(String s1, int i, String s2, int j, String s3, int k) {
        if (k == s3.length()) return true;
        mem[i][j] = 0;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) 
            if (mem[i+1][j] == 1 || (mem[i+1][j] == -1 && isInterleave(s1, i+1, s2, j, s3, k+1)))
                mem[i][j] = 1;
        if (j < s2.length() && s2.charAt(j) == s3.charAt(k)) 
            if (mem[i][j+1] == 1 || (mem[i][j+1] == -1 && isInterleave(s1, i, s2, j+1, s3, k+1)))
                mem[i][j] = 1;
        return mem[i][j] == 1;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.