# Memoization vs tabularization

• //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?

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