Memoization vs tabularization


  • 0
    Q

    //Memoization (It takes 1 ms):

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;        
        int[][] ans = new int[s1.length() + 1][s2.length() + 1];
        return isInterleave(s1, s2, s3, 0, 0, 0, ans);
    }
    
    private boolean isInterleave(String s1, String s2, String s3, int p1, int p2, int p3, int[][] ans) {
        if (p3 == s3.length()) return true;
        
        if (ans[p1][p2] != 0) return ans[p1][p2] == -1 ? false : true;
        
        if (p1 == s1.length() || p2 == s2.length()) {
            boolean res=p1 == s1.length() ? s2.substring(p2).equals(s3.substring(p3)) : s1.substring(p1).equals(s3.substring(p3));
            ans[p1][p2] = res ? 1 : -1;
            return res;
        }
        
        if (p1 < s1.length() && s1.charAt(p1) == s3.charAt(p3) && isInterleave(s1, s2, s3, p1+1, p2, p3+1, ans)) {
            ans[p1][p2] = 1;
            return true;
        }
        
        if (p2 < s2.length() && s2.charAt(p2) == s3.charAt(p3) && isInterleave(s1, s2, s3, p1, p2+1, p3+1, ans)) {
            ans[p1][p2] = 1;
            return true;
        }
        
        ans[p1][p2] = -1;
        return false;
    }
    

    //Tabularization (it takes 12 ms):

    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
        if (n1 + n2 != n3) return false;
        
        boolean[][] ans = new boolean[n1 + 1][n2 + 1];
        
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                if (i == 0 && j == 0) ans[0][0] = true;
                else if (i == 0) ans[i][j] = s2.charAt(j-1) == s3.charAt(i+j-1) && ans[i][j-1];
                else if (j == 0) ans[i][j] = s1.charAt(i-1) == s3.charAt(i+j-1) && ans[i-1][j];
                else 
                    ans[i][j] = (s1.charAt(i-1) == s3.charAt(i+j-1) && ans[i-1][j]) || (s2.charAt(j-1) == s3.charAt(i+j-1) && ans[i][j-1]);
            }
        }
        return ans[n1][n2];
    }
    

    Not sure why tabularization takes more time than memoization?


Log in to reply
 

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